💻 computer science

A Constructive Proof of Rice's Theorem and the Halting Problem via Hilbert's Tenth Problem

This paper presents a constructive proof of Rice's Theorem and the Halting Problem within intuitionistic logic by reducing them to the undecidability of Hilbert's Tenth Problem via a novel two-witness construction that avoids classical reasoning, diagonalization, and case splits on non-termination.

Original authors: Jonathan Brossard

Published 2026-04-21

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Jonathan Brossard

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: What is this paper about?

Imagine you have a magical machine (a computer program) that can look at any other machine and tell you if it has a specific "personality trait." For example, "Does this program ever stop running?" or "Does this program always output a number greater than 5?"

Rice's Theorem says: No such magical machine exists. If the trait is about what the program does (its behavior) and isn't a trivial trait (like "does it run on a computer?"), you can never build a perfect detector for it.

The Halting Problem is the most famous version of this: You can never build a program that perfectly predicts if another program will stop running or get stuck in an infinite loop.

The Problem with Old Proofs:
For decades, mathematicians proved this using "tricks" that rely on the Law of Excluded Middle (the idea that something is either true or false, with no middle ground). They used a technique called diagonalization, which is like creating a "liar paradox" (a program that says, "I will do the opposite of what you predict").

The issue: In the world of Constructive Logic (used in modern software verification and AI safety), you can't just say "It's either true or false." You have to actually build the proof. The old "liar paradox" tricks don't work here because they rely on guessing the answer before you have the evidence.

The New Solution:
Jonathan Brossard, the author of this paper, found a way to prove Rice's Theorem without using the "liar paradox" or guessing true/false. Instead, he connected the problem to Hilbert's Tenth Problem (a puzzle about solving math equations with whole numbers).

The Core Idea: The "Two-Witness" Construction

Imagine you are a detective trying to solve a mystery. The old way of proving the mystery was unsolvable was to trick the suspect into a paradox. Brossard's new way is to set up a trap using two identical-looking twins.

1. The Setup: The Diophantine Puzzle

First, imagine a very difficult math puzzle called a Diophantine equation. It's an equation where you have to find whole number solutions (like $x^2 + y^2 = z^2$ ).

The Rule: We know from a famous theorem (MRDP) that there is no general algorithm to tell if these puzzles have a solution or not. It's impossible to solve them all.

2. The Trap: The Two Twins ( $S_0$ and $S_1$ )

Brossard creates a special factory. For any math puzzle you give it, the factory builds two computer programs (let's call them Twin A and Twin B).

Scenario 1: The Puzzle HAS a solution.
- Twin A is programmed to act like a "Bad" program (one that fails your test).
- Twin B is programmed to act like a "Good" program (one that passes your test).
- Result: If you ask a detector, "Is Twin A good?" it says No. "Is Twin B good?" it says Yes. The detector sees a difference!
Scenario 2: The Puzzle has NO solution.
- Both Twin A and Twin B get stuck in an infinite loop. They both behave exactly the same: they never stop.
- Result: If you ask the detector, "Is Twin A good?" and "Is Twin B good?", it must give the same answer for both. Why? Because they are behaving identically. It doesn't matter if the detector thinks "infinite loops are good" or "infinite loops are bad"; it has to be consistent.

3. The Magic Trick: The Difference

Now, imagine you have a hypothetical "Magic Detector" that claims it can tell if any program has a specific trait.

Brossard says: "Let's feed Twin A and Twin B to your detector and look at the difference in their answers."

If the math puzzle has a solution, the detector gives different answers (1 and 0). The difference is 1.
If the math puzzle has no solution, the detector gives the same answer (0 and 0, or 1 and 1). The difference is 0.

The Conclusion:
If your "Magic Detector" actually existed, you could use it to solve the math puzzle! You would just check the difference between the twins.

Difference = 1 $\rightarrow$ Puzzle has a solution.
Difference = 0 $\rightarrow$ Puzzle has no solution.

But we already know (from the MRDP theorem) that no one can solve all these math puzzles. Therefore, the "Magic Detector" cannot exist.

Why is this "Constructive"?

In the old proofs, the mathematician would say: "Let's assume the detector works. Then we build a program that does the opposite of what the detector says. This creates a contradiction, so the detector must be broken." This relies on the idea that "It's either broken or not."

In this new proof, the author constructs a specific machine (the Twin Factory) that would solve the math puzzle if the detector existed. Since we know the math puzzle is unsolvable, the detector is proven to be impossible without needing to guess or use paradoxes. It's a direct, step-by-step construction.

The "Fuel" Analogy (Technical Detail Made Simple)

The paper uses a concept called "step-indexed models" or "fuel."

Imagine every program comes with a tank of fuel.
Every time the program does a step, it burns one unit of fuel.
If it runs out of fuel and hasn't finished, it stops (diverges).
If it finishes before the fuel runs out, it succeeds.

The author's clever trick is that the "Twins" don't just run forever; they wait to see if the math puzzle is solved.

If the puzzle is solved at step 100, the Twins switch their behavior exactly at step 100.
If the puzzle is never solved, they never switch; they just keep burning fuel forever.

This ensures that the "Twins" are perfectly identical in the "No Solution" case, making the proof watertight without needing to know why they are identical.

The Real-World Impact

Why does this matter?

Software Verification: Modern tools (like those used to verify self-driving cars or banking software) use "Constructive Logic." They can't trust proofs that rely on "maybe it's true, maybe it's false." This paper provides a proof that these tools can actually use and trust.
No "Magic" Needed: It shows that the impossibility of predicting program behavior isn't a weird logical trick; it's deeply tied to the fundamental difficulty of solving number puzzles.
The Halting Problem: Once you prove Rice's Theorem this way, the Halting Problem (can we tell if a program stops?) falls out automatically as a simple side effect. You don't need a separate, complex proof for it.

Summary Analogy

Imagine you are trying to prove that no one can predict the weather perfectly.

Old Proof: You say, "If you could predict the weather, I would build a machine that makes it rain if you say 'sunny' and sunny if you say 'rain'. This creates a paradox, so you can't predict it." (This relies on the paradox).
New Proof (This Paper): You say, "If you could predict the weather, I could use your prediction to solve a specific, impossible math equation about prime numbers. Since we know that math equation is impossible to solve, your weather predictor must be fake."

This paper builds the bridge between "predicting programs" and "solving math equations" without using any paradoxes, making the proof valid in the strictest, most logical sense.

1. Problem Statement

The paper addresses the foundational challenge of proving Rice's Theorem and the Halting Problem within intuitionistic (constructive) logic.

Rice's Theorem: States that no non-trivial semantic property of programs is decidable.
The Halting Problem: The specific instance of Rice's Theorem regarding whether a program terminates.
The Obstacle: Classical proofs of these theorems rely heavily on the Law of Excluded Middle (LEM) and diagonalization (self-reference). Specifically, they require:
1. Asserting that a constructed program either halts or diverges (LEM).
2. Performing a case split on whether the "always diverging" program ( $\bot$ ) satisfies the property $P$ (the $P(\bot)$ split).
3. Using fixed-point theorems (Recursion Theorem) to construct self-referential programs.

These classical steps prevent the proofs from being valid in intuitionistic logic, which is essential for formal verification systems like Coq/Rocq where proofs must carry computational content (e.g., for program extraction).

2. Methodology

The author proposes a novel proof strategy that avoids diagonalization and self-reference entirely by reducing Rice's Theorem directly to the undecidability of Hilbert's Tenth Problem (MRDP Theorem) rather than to the Halting Problem.

Key Technical Components:

Two-Witness Construction: Instead of constructing a single program that behaves differently based on a hypothetical decider, the author constructs a pair of programs ( $S^0_D, S^1_D$ $S_{D}^{0}, S_{D}^{1}$ ) for every Diophantine polynomial $D$ $D$ .
- Inputs: A Diophantine polynomial $D$ and two witness programs $e_0$ (failing property $P$ ) and $e_1$ (satisfying $P$ ).
- Behavior:
  - If $D$ has a solution: $S^0_D$ behaves like $e_0$ and $S^1_D$ behaves like $e_1$ .
  - If $D$ has no solution: Both $S^0_D$ and $S^1_D$ diverge identically (behave like $\bot$ ).
The Difference Function ( $\delta_D$ ): A hypothetical decider $Decide_P$ $D ec i d e_{P}$ would return different values for $S^1_D$ $S_{D}^{1}$ and $S^0_D$ $S_{D}^{0}$ if $D$ $D$ is solvable, and the same value if $D$ $D$ is unsolvable.
- Define $\delta_D = Decide_P(S^1_D) - Decide_P(S^0_D)$ .
- If $D$ is solvable, $\delta_D = 1$ .
- If $D$ is unsolvable, $\delta_D = 0$ (because $S^0_D \equiv S^1_D \equiv \bot$ , so $P(S^0_D) \iff P(S^1_D)$ by extensionality, regardless of the truth value of $P(\bot)$ ).
Step-Indexed Model: The formalization uses a step-indexed model of computation (programs are functions $N \to (N \to \text{option } N)$ ). This allows for a constructive definition of observational equivalence ( $\phi_e \simeq \phi_f$ ) without asserting that a program must either halt or diverge.
Avoidance of LEM:
- No $P(\bot)$ Split: When $D$ is unsolvable, the programs are observationally identical. The proof relies on extensionality ( $P(S^0_D) \iff P(S^1_D)$ ) rather than knowing the specific value of $P(\bot)$ .
- No Diagonalization: The programs $S^b_D$ are constructed explicitly from $D$ and a bit $b$ . No fixed-point theorem or self-reference is used.
- Implication Structure: The proof is structured as two separate implications:
  1. $D$ solvable $\implies \delta_D = 1$
  2. $D$ unsolvable $\implies \delta_D = 0$
    It never asserts the disjunction " $D$ is solvable or unsolvable."

3. Key Contributions

Constructive Proof of Rice's Theorem: The first proof of Rice's Theorem valid in intuitionistic logic that does not rely on the Halting Problem as an intermediate step. It eliminates all uses of LEM and diagonalization.
Direct Reduction to MRDP: Establishes a direct reduction from Rice's Theorem to the undecidability of Diophantine equations (Hilbert's Tenth Problem), treating the Halting Problem as a corollary.
Formalization in Rocq (Coq): The entire proof has been formalized in the Rocq proof assistant (Coq 8.18+).
- Zero Classical Axioms: The development uses zero classical axioms.
- Single External Axiom: The only external assumption is the undecidability of Hilbert's Tenth Problem ( $H10C\_SAT\_undec$ ), which is itself proven constructively in the coq-library-undecidability library.
- Verification: The formalization confirms that Rice's Theorem and the Halting Problem are "Closed under the global context," meaning they depend only on the MRDP axiom and no other classical principles.
Novelty in Witness Construction: The "two-witness" approach encodes the decision problem into the relational difference between two programs rather than a case split on a single program's behavior.

4. Results

Theorem 5.1 (Rice's Theorem): Proved that for any non-trivial semantic property $P$ , no program can decide $P$ . The proof is valid in intuitionistic logic.
Corollary 6.4 (Halting Problem): The undecidability of the Halting Problem is derived as a one-line corollary by instantiating Rice's Theorem with the property "Terminates."
Formal Verification: The Rocq formalization (1919 lines) compiles with zero errors and zero admitted goals. It confirms that the proof holds within a step-indexed model of computation.
Degree Hierarchy: The paper introduces a "Rice degree" based on the degree of the Diophantine polynomial used in the reduction, noting that degree 4 is sufficient to capture all undecidable properties (due to Matiyasevich's encoding).

5. Significance

Foundational Logic: This work bridges the gap between classical computability theory and constructive mathematics. It demonstrates that the undecidability of semantic properties is a consequence of the arithmetic complexity of Diophantine equations, not merely a result of self-reference paradoxes.
Practical Formal Verification: By removing the need for classical axioms (like LEM), this proof allows the undecidability argument to be internalized in proof assistants used for program extraction (Coq, Agda). This is crucial for verifying that certain properties cannot be decided by static analyzers within a constructive framework.
Reverse Mathematics: The paper contributes to constructive reverse mathematics by precisely identifying that the undecidability of Rice's Theorem is equivalent to the undecidability of Hilbert's Tenth Problem, without requiring stronger classical principles.
Pedagogical Shift: It challenges the standard textbook narrative that the Halting Problem is the "root" of undecidability. Instead, it posits that Diophantine undecidability is the more fundamental source, from which both the Halting Problem and Rice's Theorem flow.

In summary, Brossard provides a rigorous, constructive, and formally verified proof that semantic undecidability arises from the inherent complexity of Diophantine equations, successfully eliminating the classical logical machinery (LEM, diagonalization) traditionally required for these proofs.