Turing Machine Simulator
Build Turing Machines by defining transition rules, set up the initial tape, then step through or run the computation. Watch the tape and head move in real time. Matches AQA A Level CS (7517) specification §4.4.1.
📖 Learn Step-by-StepAdds 1 to a binary number on the tape. E.g. 1011 → 1100.
Transition Rules
| State | Read | Write | Move | Next State | |
|---|---|---|---|---|---|
| q0 | 0 | 0 | R | q0 | |
| q0 | 1 | 1 | R | q0 | |
| q0 | □ | □ | L | q1 | |
| q1 | 1 | 0 | L | q1 | |
| q1 | 0 | 1 | R | qH | |
| q1 | □ | 1 | R | qH | |
Simulator
Turing Machine Practice Questions
A Turing Machine has the rule (q0, 1) → (q0, 0, R). Starting on tape '1 1 1 □' with head at position 0, after 3 steps how many 0s are on the tape?
A Turing Machine has states {q0, q1, qH}. It has 4 transition rules. The tape alphabet is {0, 1, □}. How many entries would a complete transition table have (states × tape symbols), excluding the halt state?
A Turing Machine performs binary increment. The input tape is '1 0 1 1' (decimal 11). What decimal number will be on the tape after the machine halts?
A Turing Machine adds two unary numbers separated by a 0. Input: 1 1 1 0 1 1 (3 + 2). How many 1s will be on the tape when it halts?
A Turing Machine starts at position 0 on a tape of length 8. It moves right 5 times, then left 3 times. What is the final head position?
Quick reference — Turing Machines
What is a Turing Machine?
A Turing Machine (TM) is a theoretical model of computation consisting of an infinite tape, a read/write head, a set of states, and a transition function. It is more powerful than a finite state machine — it can recognise context-free and context-sensitive languages.
Formal definition
A TM is a 7-tuple (Q, Σ, Γ, δ, q₀, □, F) where Q is a finite set of states, Σ is the input alphabet, Γ is the tape alphabet (Σ ⊆ Γ), δ is the transition function δ : Q × Γ → Q × Γ × {L, R}, q₀ is the start state, □ is the blank symbol, and F ⊆ Q is the set of halt/accepting states.
Transition rules
Each transition is written as δ(state, read) = (newState, write, move). The machine reads the symbol under the head, writes a new symbol, moves the head left (L) or right (R), and enters a new state.
Halting
The machine halts when it enters a halt state, or when there is no applicable transition rule for the current (state, symbol) pair. The halting problem — whether a TM will ever halt on a given input — is undecidable.
Universal Turing Machine
A Universal Turing Machine (UTM) can simulate any other TM by reading its description and input from the tape. This is the theoretical foundation of general-purpose computers.