Turing Machines (TM)
An endless strip of paper, a pencil with an eraser and a short rulebook turn out to be enough to compute anything a computer can.
What this unit covers
Unit 6: Turing Machines, Decidability and Complexity
- 1 Turing Machines (TM)An endless strip of paper, a pencil with an eraser and a short rulebook turn out to be enough to compute anything a computer can. · 14 min
- 2 Variants of Turing Machines and the Church–Turing ThesisAdd tapes, add tracks, add guessing — the Turing machine shrugs and computes exactly the same things. · 14 min
- 3 Decidability and the Halting ProblemSome questions have no algorithm at all — not a slow one, not a clever one, none — and we can prove it. · 14 min
- 4 Introduction to Computational Complexity: P, NP, NP-Complete and NP-HardDecidable is not the same as doable — some problems are easy to check yet seem impossibly slow to solve. · 13 min