โ† Theory of Computation learning path
Theory of Computation ยท Module 8 of 10

Turing machines

The model of general computation.

๐Ÿ“– Key ideas

  1. A Turing machine has a finite control and an infinite tape it can read, write and move left or right on.
  2. It accepts, rejects or may loop forever.
  3. Church-Turing thesis: anything computable by an algorithm can be computed by a Turing machine.
  4. Variants (multi-tape, nondeterministic) are equally powerful.
  5. 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