Turing Machine Simulator

This repository contains a simple single-tape Turing machine simulator.

The simulator supports:

• deterministic transitions
• left/right head movement
• infinite tape
• halt state for accepting termination. Rejection is defined as any termination in a state different from halt.
• verbose step-by-step execution (⊢ notation)

---

Example Programs

1. Copy all 1s to the end

Goal

Duplicate all 1s on the tape.

Input	Expected Output
111	111111

---

2. Invert binary number

Goal

Flip all bits:

• 0 → 1
• 1 → 0

Input	Expected Output
10110	01001

---

3. Binary divisible by 3

Goal

Check whether a binary number is divisible by 3 using a modulo-3 state machine.

Input	Expected Output / Behavior
110	ACCEPT (state == halt)
1001	ACCEPT (state == halt)
111	REJECT (terminates in a state ≠ halt)

---

4. Equal number of 0s and 1s

Goal

Check whether the number of 0s on the left side equals the number of 1s on the right side.

Input	Expected Output
000111	ACCEPT
0000111	REJECT

---

How to run

python main.py transitions.txt input.txt --verbose

The simulator uses a single-tape deterministic Turing machine. The halting state is halt.

Transitions are defined as:

current_state,next_state,read_symbol,write_symbol,direction

Direction must be L or R.

Run an example:

python main.py --verbose examples/01_copy_1s_to_end/transitions.txt examples/01_copy_1s_to_end/input.txt

Run tests:

pytest -v

Theoretical background

Turing machines were introduced by Alan Turing in 1936 as a mathematical model of computation. They define the limits of what can be computed algorithmically and form the foundation of theoretical computer science [1].