Computability and logic · existing Mathlib theorem
Undecidability of the Halting Problem
Fix one input and vary the encoded program. No single computable test can correctly decide for every code whether its evaluation on that input eventually returns a value.
Accepted Atlas resultNot recorded for the preferred artifact
These states distinguish upstream identity, local reproduction, review, and Atlas acceptance. This page is part of the public, read-only Mathlib landmark collection.
Formal orientation
Statement map
This deterministic map orients the reader from the mathematical summary to the pinned declaration and exact checked form. The HTML statement below is authoritative.
The theorem at a glance
The Halting Problem at a glance
A source-bound editorial overview of the exact Mathlib formulation. The image is explanatory; the statement map, formal type, and pinned source remain authoritative.
No computable predicate decides defined evaluation for every code at a fixed input. Generated explanation only; the exact HTML statement and pinned source are authoritative.Detailed visual description
The poster separates the theorem's fixed input and encoded-program quantification from the two Rice witnesses, making noncomputability rather than long running time the central conclusion.
Halting Problem schematic
Loading full-resolution image…
A computable fixed-input halting classifier would decide a nontrivial semantic property forbidden by Rice's theorem.Open original image in a new tab ↗
A computable fixed-input halting classifier would decide a nontrivial semantic property forbidden by Rice's theorem. Generated explanation only; the exact HTML statement and pinned source are authoritative.Detailed visual description
The same fixed input passes through a proposed classifier with varied program codes. One computation resolves to a defined endpoint and another remains nowhere defined, making the semantic distinction nontrivial before the contradiction folds back on the classifier.
Complementary intuition
A mathematical landmark
Halting undecidability marks a fundamental limit on algorithmic prediction. Mathlib's theorem proves an exact fixed-input version for its own code and partial-evaluation model through Rice's theorem.
The low-text schematic gives the theorem a visual identity; it does not replace the source-bound poster or exact statement.
A Rice-theorem proof of fixed-input halting undecidability
2 curated stages
Mathlib fixes one input and treats defined evaluation as a semantic property of encoded partial-recursive programs. Rice's theorem rules out a computable classifier once the defined zero function and the nowhere-defined function witness that the property is nontrivial.
These source-anchored stages explain the retained Mathlib proof route. They are generated explanations, not proof evidence or an extracted Lean proof-term dependency graph.
01
A proposed decider classifies codes by their behavior at one input
A proposed decider classifies codes by their behavior at one input
Loading full-resolution image…
Fixing n, the hypothetical computable predicate would separate exactly the codes whose partial evaluation at n is defined.Open original image in a new tab ↗
Fixing n, the hypothetical computable predicate would separate exactly the codes whose partial evaluation at n is defined.
ComputablePred (fun c ↦ (c.eval n).Dom)
The selected theorem fixes a natural-number input and varies Mathlib codes c. Its contradiction assumption is a computable predicate for the semantic class of partial-recursive functions defined at that input, the precise input required by ComputablePred.rice.
02
One witness halts and one never returns
One witness halts and one never returns
Loading full-resolution image…
The zero function belongs to the fixed-input halting class while the nowhere-defined function does not, so Rice's theorem rejects the decider.Open original image in a new tab ↗
The zero function belongs to the fixed-input halting class while the nowhere-defined function does not, so Rice's theorem rejects the decider.
¬ComputablePred (fun c ↦ (c.eval n).Dom)
The one-line proof supplies Nat.Partrec.zero and Nat.Partrec.none to Rice's theorem. The first computation is defined at the fixed input; the second has no value there. A computable classifier for this nontrivial semantic difference would contradict Rice's theorem.
Claim boundary
No new theorem is claimed
This target indexes Mathlib's encoding-specific theorem that, for a fixed input n, the predicate saying a coded computation c halts on n is not computable. It does not quantify over arbitrary machine models or claim a new undecidability proof.
Proof Atlas did not originate the halting problem theorem or Mathlib's declaration.
The formal scope is Mathlib's encoded programs and evaluation relation at a fixed input, not every machine formalism simultaneously.
The generated explanation and visuals are not proof evidence.
