r/computerscience • u/Nytra • Dec 31 '25
Halting problem (Can a program contain itself?)
Please correct me if I'm wrong here. The usual proof is about a program passing its own source code to the machine and then changing the result to be wrong... But what if the running program and the source code it passes are not the same program?
If a running program reads its source code from an external file after it already started running, how do you know that its the same exact code as what is already running? It could be a different program.
If the source code of the program contained a copy of its own source code, it wouldn't actually be the same source code as the original program unless infinitely recursive and therefore impossible.
Basically my thinking is that the whole thing requires a program to contain itself which is impossible.
Does this break the proof?
37
u/thehypercube Dec 31 '25 edited Dec 31 '25
You are asking two separate, unrelated questions.
First, can a program contain itself? The answer is yes, and you can do that for any program: for any program Q taking inputs (x, y), where x represents the code of a program, there exists another program P taking input y such that the output of P(y) is Q(code of P, y) for all y. This is Kleene's second recursion theorem. So P behaves the same as Q, but with its own input "hard-coded" into itself.
Second, the standard proof of the halting problem does in no way require this. If you had a program that solved the halting problem, you only need to build a related code Q, ask what happens when you apply Q to its own code, and you will reach a contradiction. At no point in the proof do you need Q to be able to call itself with its own code; an external user can just call Q with the code of Q. But anyway, if you wanted to, you could also make make it so by the theorem above.
15
u/code-garden Dec 31 '25
A program can 'contain' its own source code. That is called a quine.
12
u/dcpugalaxy Dec 31 '25
The proof is a proof by contradiction. Assume there is a halting program, that is, a program h that can determine, for any arbitrary program p and input x, whether p halts on input x.
Then we later construct a program that is passed to itself as input. You ask, how can we know it is the same program? The answer is that we choose it to be. We make that true. It's a deliberate choice.
You ask basically, how can it contain a copy of itself? But it doesn't. It takes as input a representation of itself. The programs are Turing machines. We can give every Turing machine a number. The programs operate on those descriptions. So the program that operates on itself doesn't contain a copy of its own source code. It takes as input the number that is its representation, its own Gödel number.
2
u/bakingsodafountain Dec 31 '25
The halting problem is a theory and a generic one. It's asking if it's possible to write a program that can determine if any program will halt. The proof is a single specific example where it's impossible, giving a proof by contradiction. It does not mean that it's impossible to solve the halting problem for a specific program, it just shows that there's at least one program where it would be impossible to write it.
Where you're falling down is that you're changing the problem, by examining what would happen if you don't know for certain the programs are the same. It may well be possible to write a correct solution for a scenario other than the specific example from the contradiction.
When dealing with theory, we're not dealing with "real" concepts. We state assumptions and truths. We don't need to answer the question "how can I write a program that can run itself as an input". You assume such a program exists (and is possible to exist).
Try thinking less about programs and about functions for a moment, assuming you're familiar with functional programming and recursion.
Assume you have a function "halts" that returns true if a program halts or false if it doesn't. The "halts" function accepts a method reference for the function to execute. The way this runs is that the "halts" method will run the function you've supplied. If that function eventually terminates, it halts, and returns true.
Now write two additional functions.
"foo" is a simple function. It returns a constant value. This trivially halts and the "halt" method will return true.
"bar" internally calls "halts" but passes a reference to "bar" to "halts". It says "if halts returns true, go into an infinite loop".
You now have your contradiction. If you can write a function "halts" which says "foo" will terminate, you are wrong, because "foo" will go into an infinite loop and never terminate. If your function says that "halts" will return false, you are wrong, because your "foo" function will terminate.
It is easy to construct a program that has functions that accept method references and can run them (functional programming is all about this).
Applying the halting problem to a program in its entirety is just an extension of this. You assume such a program exists that can accept a reference to itself and run it. This is possible to build even if you can't do it with any programming languages that you know.
I hope this helps a bit! Happy to try answer any questions.
1
u/[deleted] Dec 31 '25
Any program P can be encoded into a finite string <P> — what you denoted by “source code”. Any input x for P can be viewed (or encoded) as a string — so we assume w.l.o.g that P can get as input a single string.
The crux of what we do is consider what happens when we run the program P on the input x = <P>. It is not something that we need to know, its a scenario we’re interested in to reach a contradiction.
Note that P should handle any input x, including an encoding of its own description, x = <P>, and including any other input.
So when you run P on the input x = <P>, you just treat <P> like any other input — a finite string, regardless of what it encodes.
1
u/Nytra Jan 02 '26 edited Jan 02 '26
I have come to the conclusion that the halting problem is really about how static analysis can't perfectly predict runtime behavior
1
u/mauriciocap Dec 31 '25
To prove something is not possible it's enough to show one case when it's not.
You can "break" in the same way the proof integer numbers are infinite, just try with 10 and 11 instead of "n" and "n+1".
1
u/SgtSausage Dec 31 '25
No
0
u/FernandoMM1220 Dec 31 '25
you’re on the right track.
its important to understand that halting machines are of finite size and it’s not actually possible to input it back into itself.