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.