Turing machines
(2.5 hours to learn)
Summary
Turing machines are a simple theoretical model of computation involving a head which reads and writes symbols on a tape. Despite its simplicity, if the Church-Turing Thesis is true, then anything which can be computed, can be computed by a Turing machine. They are a fundamental construct in reasoning about the limits of computation.
Context
-this concept has no prerequisites-
Goals
- Define a Turing machine
- Be able to write Turing machines to solve simple problems
- Be aware of universal Turing machines
- Be aware of the Church-Turing thesis
Core resources (read/watch one of the following)
-Free-
→ Coursera: Automata
An introductory course on automata and the theory of computation.
Location:
Lecture "Turing machines"
Other notes:
- Click on "Preview" to see the lecture videos.
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
- Section 3.1, "Turing machines," pages 137-147
- Section 3.3, "The definition of algorithm," pages 154-159
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
- Section 8.2, "The Turing machine," pages 324-335
- Section 8.3, "Programming techniques for Turing machines," pages 337-343
Other notes:
- Read Section 8.1, "Problems that computers cannot solve," for some motivation.
See also
-No Additional Notes-