New Tool

Turing Machine Visualiser

Build a Turing machine, define your own transition rules, and watch the read/write head step across an infinite tape. Use the presets to explore classic problems, or write your own from scratch.

A-Level Theory of Computation
AQA Computer Science
OCR H446
Infinite tape
Animated head
Editable rules
Preset
Start State
Tape Input (blank = □ or leave empty)
State q0
Step 0
Status Ready
Reading --
Head at 0
Speed:
State Diagram
Transition Rules
Current State Read Symbol Write Symbol Move Next State
Execution Log
Execution log will appear here when you step or play.

Exam Tips: Turing Machines

  • What is a Turing machine? A theoretical model of computation with an infinite tape divided into cells, a read/write head, a finite set of states, and a transition function. It is not a real machine -- it is a mathematical concept.
  • The transition function takes the current state and the symbol under the head, then specifies what to write, which direction to move (L or R), and what state to enter next.
  • The blank symbol (□) fills all unwritten cells. It is part of the tape alphabet. In this tool it is represented internally as an underscore and displayed as □.
  • Halting states are special states where the machine stops. A machine accepts if it halts in an accept state and rejects if it halts in a reject state or if no transition exists for the current configuration.
  • Church-Turing thesis states that any effectively computable function can be computed by a Turing machine. This is why Turing machines are used to define what is and is not computable.
  • The Halting Problem -- can a Turing machine decide whether any given Turing machine will eventually halt? -- was proved by Turing to be undecidable. No algorithm can solve it in general.
  • Turing complete means a system can simulate any Turing machine. Modern programming languages are Turing complete.
  • Exam note: At A-Level you may be asked to trace a Turing machine by completing a table showing the tape contents, head position, and state at each step. Practise stepping through this tool one step at a time.