Turing Machines

• Each square has a symbol from a finite alphabet

• A datum

• Has a read-write head

• Reads a symbol

• Symbol + current state

• Writes a new symbol
• Moves left or right on the tape