Turing Machines

• Why interesting?

• Surprisingly powerful

• Can perform all `conventional' computations

• Extensions are equivalent to original model

• Other models equivalent to Turing Machines