• Overview
• Details
• Exercises

Turing machines formalize computation and define the notion of algorithm. Key ideas include universality, decidability vs. undecidability, and reductions. The halting problem is a canonical undecidable problem.

• Turing machine (TM): states, tape alphabet, transition function; variants (multi-tape, nondeterministic) are equivalent in power.
• Decidable/recognizable languages: decider halts on all inputs; recognizer halts on members, may loop otherwise.
• Universal TM and Church–Turing thesis; encoding machines as strings.
• Undecidability: Halting problem, diagonalization; Rice’s theorem (nontrivial semantic properties are undecidable).
• Reductions: mapping/Many-one reductions; using reductions to prove (un)decidability.
• Time/space complexity preview; relationship to complexity classes introduced later.

1. Describe a TM that recognizes L = { 0^n1^n | n ≥ 0 } using a marking strategy; argue correctness.
2. Prove the halting problem is undecidable via diagonalization. Then give a reduction from HALT to another problem.
3. State Rice’s theorem and use it to show that “does TM M accept any string?” is undecidable.