A Constructive Proof of Rice's Theorem and the Halting Problem via Hilbert's Tenth Problem
cs.LO, cs.CR
Submitted: 2026-04-11
Updated: 2026-10-29
Comments: 46 pages, Rocq (Coq 8.18+) formalization included. Source and C witness: https://github.com/endrazine/rice-constructive
Code: https://github.com/uds-psl/coq-library-undecidability
License: http://creativecommons.org/licenses/by/4.0/
The gist: Rice's theorem states that no non-trivial semantic property of programs is decidable.
Terminology
Abstract
Rice's theorem states that no non-trivial semantic property of programs is decidable. Classical proofs proceed by reduction from the halting problem, invoking the law of excluded middle (LEM) twice: once through diagonalization, and once through a case split on whether the always-diverging program bot satisfies the property in question. We present a proof that is constructive relative to the undecidability of Hilbert's Tenth Problem (MRDP): valid in intuitionistic logic, requiring neither diagonalization nor self-reference, and adding no classical reasoning beyond the MRDP assumption itself. The key idea is a two-witness construction. Given a non-trivial property P, we attach to each Diophantine polynomial D a pair of programs S 0 D, S 1 D that behave like the negative and positive witnesses for P when D is solvable, and both diverge identically when it is not. A hypothetical decider for P would therefore decide Diophantine solvability via the difference delta D = DecideP(S 1 D) - DecideP(S 0 D) -- contradicting the MRDP theorem. The argument is structured as two separate implications, never asserting a disjunction about solvability, and never examining P(bot). The undecidability of the halting problem follows as an immediate corollary: a single application of Rice's theorem to the Terminates property. A formalization in the Rocq proof assistant confirms both results within a step-indexed model of computation, with the undecidability of Hilbert's Tenth Problem as the sole external axiom. Both Rice Theorem and Halting Problem are closed under the global context.
Sources
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring