Undecidability of the halting problem
No total algorithm decides halting for every program and input in a general computation model.
Key knowledge
There is no algorithm that always terminates and correctly decides, for every program-input pair in a Turing-complete computation model, whether that program eventually halts on that input.
Conditions and scope
- The theorem concerns unrestricted programs in a general model with unbounded potential memory and running time.
- It does not rule out deciding specific programs or restricted classes, nor checking execution within a fixed resource bound.
Sources · 4
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
General undecidability theorem and diagonal argument.
2026-10-10 · Compared formal register-machine statement with an independent program-level argument; no claim about all restricted languages.
Foundational review
2026-10-10 · Fresh primary-source inspection of the complete compact record, including every statement, equation, quantity and material condition, followed by independent AI editorial review. This check does not certify all linked lessons or every passage of every cited publication.
Sources from other places
Agreement within this scope
No general algorithm decides halting for every program/input pair.
The program model incorporates inputs as natural numbers; bounded or restricted cases are outside the theorem.
University of Auckland, Department of Computer Science
- Lectures on Philosophy and Computation New ZealandEnglish
Slides 4–6 (PDF pp.4–6)
- Lectures on Philosophy and Computation
Entry details
Permanent link to this entry ↗- Record identity
- info-halting-problem
- Revision
- core.1
- Structured reference record
- Essential core · first collection