Theoretical CS

4.3 Turing Machines

A Turing Machine, invented by Alan Turing, is another theoretical model of computation that is more complex than DFAs and NFAs. In fact, a Turing Machine can simulate any given computer algorithm, and is used to prove the fundamental capabilities and limitations of computers.


A Turing Machine consists of two main “parts”: an infinite tape of symbols, and a machine that can read, write, and move the tape one symbol at a time. This machine keeps track of states and transitions, and can be visually represented with a graph, much like DFAs.

We will study how to read and write Turing Machine algorithms.

<< 4.2 Deterministic Finite Automata 4.4 Computational Complexity >>