Turing Machines

• Simple theoretical model

• computability

• Basis of modern computers

• Finite state machines

• Equivalent to a digital computer

• Deal with an infinitely long tape

• Tape has a finite number of non-blank squares