I was reading through the proof for the halting problem and saw that that the "pathological" program that makes program H return the wrong result needs to have H inside it, where H is a program that solves the halting problem. I was thinking if it were possible to make a program H* that could solve the halting problem for all programs that do not contain H* inside of them.
Let's say we have 2 sets of programs.
(1) Programs that are H*-like, which has an output based on whether an input program halts or not.
(2) Programs that are not H*-like, which have an output not based on whether an input program halts or not.
Would it be possible to construct a program H* that can solve the halting problem for all programs in Set (2)?
-
$\begingroup$ Hi π, interesting question! It is not entirely clear to me though what "output is based on whether an input program halts or not" formally means. Do you have a concrete definition in mind? $\endgroup$Knogger– Knogger07/05/2025 21:49:23Commented Jul 5 at 21:49
-
$\begingroup$ Hello! The definition I had in mind for an H*-like program was a program that takes in another program P as input, and if program P halts it does one thing, and if program P doesn't it does something else. @Knogger $\endgroup$Aliesha Flynn– Aliesha Flynn07/05/2025 21:55:47Commented Jul 5 at 21:55
-
$\begingroup$ What does it mean exactly, for a program to do different things in each case? Does it produce different outputs? Must it halt in one case and loop in the other? $\endgroup$Knogger– Knogger07/05/2025 22:47:34Commented Jul 5 at 22:47
-
$\begingroup$ Yes to both, as long as the program does something different depending on whether P halts or does not halt. @Knogger $\endgroup$Aliesha Flynn– Aliesha Flynn07/05/2025 23:18:08Commented Jul 5 at 23:18
1 Answer 1
The problem is that the distinction you are trying to draw isn't actually precise: how do you define what a program's behavior is "based on"?
To see that this is a real problem and not just nitpicking, consider the following setup. Given $(n+1)$-variable (some fixed $n$ is enough - I vaguely recall $n=31$ being current state-of-the-art) polynomials $p,q$, let $B_{p,q}$ be the program which on input $k$ performs a brute-force-search for an integer solution to $p(k,x_1,..., x_n)=q(k,x_1,...,x_n)$ and halts iff such a solution exists. There's certainly no built-in reference to other programs' halting behavior in $B_{p,q}$. However, by the MRDP theorem, we can in fact simulate arbitrary halting problems in this way: for every machine $M$ there is some pair of polynomials $p,q$ such that $B_{p,q}$ halts on exactly the same inputs that $M$ does. In particular, we get that even for programs of the form $B_{p,q}$ the halting problem is undecidable.
Of course this doesn't prevent us from identifying large classes of programs for which the restricted halting problem is simple, e.g. classes of always-halting programs like the programs which only use primitive recursion or those provably total in some fixed theory. But the idea of singling out "bad" programs based on their referents is, while intuitively attractive, not currently something that we have the mathematical machinery to actually do. (Similarly, there is no real sense currently of when a sentence in the language of arithmetic is "truly" self-referential a la Godel; self-reference is a property of the way we constructed/found the sentence in question rather than the sentence itself.)
Explore related questions
See similar questions with these tags.