Computer Science › Section M · Theory of computation › Topic M.4
A noncomputable function: the halting problem
Wouldn't it be useful to have a tool that checks any program and tells you whether it will ever stop? This topic proves that no such tool can exist, on any computer, now or in the future: the halting problem has no algorithmic solution.
In this topic
- A tool that cannot exist
- The halting problem
- Worked example: deciding particular programs
- Why running it is not enough
- Programs as inputs
- The assumption and the trap
- Worked example: the contradiction
- What the proof does and does not say
- More undecidable problems
- Living with the limit
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…