AQA 7517 4.4.5.1: Turing machine
The free BugBot lesson that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
To prove the Halting problem had no solution, Turing first had to say exactly what "an algorithm" is. His answer, in 1936, was an imaginary machine simple enough to reason about and powerful enough to carry out any algorithm at all. It is still the model computer scientists use to define what can be computed. A finite state machine is the control unit of a Turing machine; the Turing machine adds the one thing an FSM lacks, unlimited memory.
- The parts of a Turing machine
- Transition functions
- State transition diagrams
- Hand-tracing
- A Turing machine in Python
- The universal Turing machine
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A6.9 Turing machines Theory of computation
Tape, head, states and transition functions; tracing a Turing machine; the universal Turing machine and why it matters.
Try it on a robot
The task from A6.9 Turing machines, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.4.5.1 and is not endorsed by the board.