โ Theory of Computation learning pathTheory of Computation ยท Module 8 of 10
Turing machines
The model of general computation.
๐ Key ideas
- A Turing machine has a finite control and an infinite tape it can read, write and move left or right on.
- It accepts, rejects or may loop forever.
- Church-Turing thesis: anything computable by an algorithm can be computed by a Turing machine.
- Variants (multi-tape, nondeterministic) are equally powerful.
- A universal Turing machine simulates any other Turing machine from its description, the idea behind stored-program computers.
๐ก Real-life example: A Turing machine is like a person with a pencil, an eraser and an endless paper strip, following a fixed rule book.
Turing machineAutomaton with an infinite read-write tape
Church-Turing thesisAlgorithms equal Turing-computable functions
Universal Turing machineTM that simulates any other TM
HaltingMachine stopping in accept or reject