Turing Machine Studio
Simulate pre-built TMs or design your own with the interactive canvas. AQA A Level CS (7517) §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.