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.
Author: Jeffrey D. Ullman
Other notes:
  • Click on "Preview" to see the lecture videos.

-Paid-

See also

-No Additional Notes-