Computer Science › Section M · Theory of computation › Topic M.2
Turing machines
A Turing machine is little more than a tape, a head and a short table of rules, yet as far as anyone knows it can compute everything any computer can. That makes it the yardstick computer scientists use to measure what is computable at all.
In this topic
- A model of a person computing
- The parts of a Turing machine
- One step at a time
- A machine that adds
- Worked example: tracing the adder
- Worked example: an even-parity checker
- Computing functions, and never halting
- The Church–Turing thesis
- Why the yardstick matters
- The universal machine
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…