Existing in Mathlib · Computability and logic

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.

computable predicate
partial recursive function
program code
defined evaluation
Rice's theorem

Exact theorem

Exact Mathlib statement

theorem ComputablePred.halting_problem (n : ℕ) : ¬ComputablePred (fun c ↦ (c.eval n).Dom)

The theorem at a glance

The Halting Problem at a glance

A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.

An ivory computability poster shows abstract program sheets, one fixed input, a bifurcating proposed classifier, defined and nowhere-defined trajectories, and the fixed-input scope. — No computable predicate decides defined evaluation for every code at a fixed input.

Statement structure

Statement and scope

Read the exact Mathlib declaration

This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.

Scientific figure illustrating: A computable fixed-input halting classifier would decide a nontrivial semantic property forbidden by Rice's theorem. — A computable fixed-input halting classifier would decide a nontrivial semantic property forbidden by Rice's theorem.

Why it matters

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.

Proof architecture

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.

A proposed decider classifies codes by their behavior at one input
A proposed decider classifies codes by their behavior at one input
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.
One witness halts and one never returns
One witness halts and one never returns
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.

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally

Locally reproducedExact upstream declaration replayed

Reviewed pageCurrent public presentation reviewed

Accepted Atlas resultNot recorded for the preferred artifact

Mathlib is the source of the theorem; the local Lean replay and page review are separate.

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.

Source and local evidence

Where the theorem comes from

Existing declaration: ComputablePred.halting_problem in mathlib
Relationship: The checked artifact is the upstream declaration itself
Local Lean evidence: artifact.library.mathlib.halting-problem.v001
Source: Open the pinned upstream reference