> ... because computers aren't Turing machines and have finite memory, so all programs are guaranteed to halt.
Is this simply wrong or am I not understanding? With finite memory, the halting problem is solvable, but that's different than all programs halt.
while True:
pass
The program doesn't halt even with finite memory. Unless he means eventually the world will end, or the power supply will die, etc.
> If the halting problem was solvable, then anyone with a computer could prove Goldbach's conjecture in an afternoon.
Why does he say "in an afternoon"? Maybe it would take 10^100 years? The halting problem be solvable or unsolvable is not a question of complexity or efficiency.
Yeah, I stumbled over that too. I think they meant to say any “interesting” program would halt. Programs that don’t halt will repeat state (in your example there isn’t even any state, so it’s trivially always the same), and the article wants to look at programs where we run out of state (and also describes why it isn’t interesting to halt when hitting the state size limit).
The gist of the article is of course correct, but it uses some terminology wrong. "Recursively enumerable" and "decidable" aren't applicable to instances of individual programs. In fact, every single instance of a problem is "decidable" because either the program that always returns true or the one that always returns false solves it (we don't necessarily know which one, but that isn't required). And in any case, for the Goldbach conjecture, the set of numbers that satisfy it is decidable - the function sum_of_two_primes is such a decision procedure.
What's undecidable is the set of valid conclusions (from some axioms) in first-order logic (in short, "FOL is undecidable"). So there is no algorithm that can tell us whether a given mathematical statement (including Goldbach's conjecture) is "true" (i.e. follows from the axioms of arithmetic, or ZFC, or something). FOL is recursively enumerable, since we can just generate all possible proofs.
Similarly, the set of halting programs isn't decidable, but it is recursively enumerable (every halting program halts at some time t, now enumerate all pairs (program, t) via a diagonal argument and check if program halts within t steps).
Someone discovered the halting problem again. Sigh.
First, the halting problem only applies to systems with infinite memory. If memory is finite and the system is deterministic, the program will either halt or repeat a state. The halting problem is thus decidable for non-infinite systems. So there.
The next question is whether there are programs with lower time bounds that can be made arbitrarily large. Actually, we don't know the answer to that. Cryptography assumes the answer is yes, but that's an assumption. We don't actually know that factoring is inherently hard, only that enough people have beaten on the problem that we know there's no easy to find shortcut.
Proof of correctness systems run into the complexity problem. You can write things that force a SAT solver to explore so many cases that it won't finish in any reasonable time. But that's not undecidability. My usual comment on this is that if your program is unreasonably hard to test for termination, it's broken. Microsoft takes that position with their Static Driver Verifier. There's a timeout; if it takes too long to prove your kernel driver safe, it doesn't get signed for use in the kernel.
> A lot of people use the proof that the halting problem is undesirable to make some deep philosophical point
Penrose comes to mind. There are people who are desperate to prove that humans transcend computers in some fundamental way. We heard a lot more from that crowd before LLMs started writing better than some of their critics.
> First, the halting problem only applies to systems with infinite memory. If memory is finite and the system is deterministic, the program will either halt or repeat a state. The halting problem is thus decidable for non-infinite systems. So there.
The article mentions this fact specifically in about the third paragraph, and goes on to talk about why it's less relevant than it might appear.
> The next question is whether there are programs with lower time bounds that can be made arbitrarily large. Actually, we don't know the answer to that.
No, the time hierarchy theorems prove that such programs exist.
> My usual comment on this is that if your program is unreasonably hard to test for termination, it's broken. Microsoft takes that position with their Static Driver Verifier. There's a timeout; if it takes too long to prove your kernel driver safe, it doesn't get signed for use in the kernel.
Timeouts make it much harder to reason about programs and perform safe refactors, because the class of refactors that are guaranteed to not break a program becomes quite small. E.g. you can no longer prove that "val y = f(x); g(y)" is correct if "g(f(x))" is correct and vice versa.
> The next question is whether there are programs with lower time bounds that can be made arbitrarily large. Actually, we don't know the answer to that. Cryptography assumes the answer is yes, but that's an assumption.
Cryptography does not assume that. It only needs a certain amount of slowness, and a large polynomial like n^20 is more than sufficient. But more importantly the best case for cryptographic security is exponential time. Cryptography ignores the entire science of super large numbers.
To really boil down what cryptography needs, it's problems that take ≤2^40 operations to verify but ≥2^200 (irreversible) operations to solve. It doesn't actually need to scale at all.
Also it's not hard to make programs that take huge amounts of time. In particular, a program that uses exponential time and leaves an exponentially long output is downright trivial to write. In pseudocode: while(i++ < 2^n) output.append(1)
> If memory is finite and the system is deterministic, the program will either halt or repeat a state. The halting problem is thus decidable for non-infinite systems.
While this is theoretically correct, there are offensively short programs for which we can't (yet) decide if they terminate or loop infinitely. E.g. Collatz conjecture offers such a program that does not even require a colossal state to track during execution, its state is one integer.
Sadly there are problems that are theoretically decidable but cannot be practically decidable, because the required computation would take the resources of the entire universe, and would take longer than it's projected to exist (at least in a state that can support computation).
The next question is whether there are programs with lower time bounds that can be made arbitrarily large.
It's not precisely the same as "arbitrarily large", but this is the practical result given the busy beaver function. Following from that, yedidia and Aaronson proved the existence of BBs outside of ZFC that are smaller than almost all real programs. I'd consider that essentially what you're complaining is unproven here.
This is a rant I’ve had in my head forever, so thanks for posting this. A lot of people use the proof that the halting problem is undesirable to make some deep philosophical point, like this one. But the actual proof is so disappointing and non-philosophical that I wonder if anyone making these grand statements has ever read it. It just invents a program which outwits the halting detector by doing the opposite of what it would otherwise say.
Its like, if you met the smartest person in the world, and you asked them “will you answer no to this question” and then no matter what they said you laughed in their face and said hah, guess you’re not so smart, are you?
And THAT is why you think we don’t live in heaven?
Like, OP says that because of this proof we can’t run HALT() on a program that assets the Goldbach conjecture. What? That’s entirely orthogonal from the proof of the undecidability of the halting program, unless one of the primes has embedded a trick logic question into itself somehow. There’s nothing stopping there from being a “HALT_FOR_EVERY_PROGRAM_EVER_EXCEPT_THAT_ONE_TRICK_PROGRAM”. There you go, you’re back in heaven again!
Kolmogorov complexity is undecidable because the halting problem is undecidable. If we could solve Kolmogorov complexity we could do Solomonoff induction and build AIXI and solve (at least one formulation of) decision theory.
The real problem (imo) is that proof search is also undecidable (either directly from halting problem or similar argument) and so there isn't a procedure we can write that identifies trick programs to exclude as special cases. There are an infinite number of various trick programs for which halting is undecidable and recognizing them is undecidable.
> There’s nothing stopping there from being a “HALT_FOR_EVERY_PROGRAM_EVER_EXCEPT_THAT_ONE_TRICK_PROGRAM”.
Doesn't work that way. If we have "HALT_FOR_...EXCEPT_THAT_ONE_TRICK_PROGRAM", then we can simply create "HALT_FOR_ACTUALLY_EVERY_PROGRAM" by:
if (is this that one trick program?) then
return THE CORRECT ANSWER FOR THAT TRICK QUESTION, HARD-CODED
else
answer = HALT_FOR_EVERY_PROGRAM_EVER_EXCEPT_THAT_ONE_TRICK_PROGRAM()
return answer
...but this is impossible, because then it would actually solve the full halting program, and we know it's impossible.
So the best you can have is "Solve the halting problem for a bunch of programs, but not for a bunch of others, but that's okay because will call the latter as 'trick programs.'"
And the problem is that you can't give a mathematically satisfying definition of what is a trick program, and whatever you try, you'll likely end up defining a lot of actually interesting programs as trick programs. So it's actually "Solve the halting problem for some programs, but not others." And that's not terribly interesting, because we already know it's possible.
I am probably not the only one who finds the above as pointless as trying to determine whether the sentence "this sentence is false" is true or false. It is neither, but most of the time we're interested in problems that have answers, and that problem space turns out to be huge and extremely useful.
What are some good examples of practical programs that aren't trying to create a chain of computation that is ultimately circular and self-referential yet still run into trouble with the halting problem?
> What are some good examples of practical programs that aren't trying to create a chain of computation that is ultimately circular and self-referential yet still run into trouble with the halting problem?
Almost any unproven mathematical conjecture, e.g. a program that searches for counterexamples to the Riemann hypothesis. More practically, a lot of problems reduce to SAT, so these days quite a lot of systems work by just running a SAT solver on the problem (e.g. dependency resolution in some build systems), and it's fast most of the time but you can never be sure it's not going to get stuck.
> Almost any unproven mathematical conjecture, e.g. a program that searches for counterexamples to the Riemann hypothesis.
This is a very good example. We don't know whether such programs will ever stop, and knowing is exactly equivalent to resolving the conjectures.
> More practically, a lot of problems reduce to SAT, so these days quite a lot of systems work by just running a SAT solver on the problem (e.g. dependency resolution in some build systems), and it's fast most of the time but you can never be sure it's not going to get stuck.
This is a less good example because SAT solvers can always run in finite time and can be proven to halt. Even if they do "get stuck", they will take exponential time rather than infinite time.
There are probably some problems that arise practically that are undecidable in general (e.g. type checking for sufficiently expressive type systems), but problems that "reduce to SAT" are never examples of such undecidable problems because SAT is decidable.
I was going to say the same thing about SAT, or any NP-hard problem.
The first example doesn't seem to be good either however. I don't think that proving a mathematical conjecture which has resisted proof for decades (or longer) is something that we would typically expect a computer program to be able to do. Whenever this happens, it is hailed as a major breakthrough.
The point is that it can complicate analysis of a program, at least if you take the fundamentalist view that all program behaviour should be provably correct. Like if you need the collantz sequence of a number or something in your program, you would just calculate it and use it, but it's surprisingly hard to prove that it always exists. Which isn't so much a problem in itself as it complicates trying to prove anything else about your program's behaviour.
> So the best you can have is "Solve the halting problem for a bunch of programs, but not for a bunch of others, but that's okay because will call the latter as 'trick programs.'"
The awesome and surprising thing is, I’ve actually written such a program! It regularly runs the program to test, but stops and screams “trick program!” if the program to test did not finish within five minutes. Sadly, I haven’t been awarded my Fields Medal yet, probably because I didn’t use LLMs.
The philosophical issue is there are questions which seem "simple" and have answers, but even if given the answer you could not know whether it was the right answer.
The halting problem is more than that. While the proof constructs a relatively trivial Turing machine that basically puts the toddler's "Nuh-uh!" on solid mathematical ground, that's just the proof that there exists at least one Turing machine for a given halting oracle that can not be predicted by that halting oracle.
It is true that the halting problem itself is perhaps not directly what people seem to think it is, but people turn out to be right anyhow, because Rice's Theorem can be largely summed up as "It can be proven that we can not have nice things", if you'll allow me a bit of mathematician-style humor, which corresponds more-or-less to the way people talk about the Halting Problem.
This also explains why the Goldbach conjecture is in fact directly related to the halting problem and not orthogonal at all. Through Rice's theorem we can extend the halting problem quite easily to the solution to that and a lot of other problems.
By computer science standards, Rice's theorem is relatively basic stuff. I don't recall if the sophomore-level class I learned about this stuff did a full proof of Rice's theorem but I certainly recall several homework problems around applying the idea of the theorem to several specific problems by proving reductions of those problems to the halting problem. I also recall they really weren't particularly difficult problems. It's not hard to reduce that sort of interesting question to the halting problem. Low-level undergrad stuff, stuff down in the very basics of computer science qua computer science suitable for making up several problems in the weekly homework assignment for the intro to (real) computer science course, not complicated abtruse stuff that can't be applied by anyone less than a doctoral candidate with a few months to burn. All sorts of problems are reducible like this.
And that is why the "halting problem" in fact is the reason why we can't have certain nice things we'd really like. For example, the mentioned ability to prove that two functions really are equivalent would have practical utility in a wide variety of places (assuming somewhat reasonable efficiency), like compiler optimizations.
Your intuition is correct in one respect though; there is a sense in which it isn't really "The Halting Problem (TM)". You could take a wide variety of other problems and call them "the" fundamental problem, and reduce the halting problem to those problems. The Halting Problem just turns out to be a particularly concise specific expression of the general problem that is easy to express for Turing Machines. It just makes for nicer proofs than the alternatives. "The" core problem could arguably be something more like Rice's Theorem proved on its own as a fundamental proof without reference to the halting problem. You could call the Halting Problem a historical accident that we hold on to due to a path dependency in how math happened to develop in our history. An alien race might have a reasonably different view on the "fundamental problem", but then they'd have a something fairly similar to Rice's Theorem sitting on top of it that we'd all recognize.
Yeah, it's fundamentally a "if god can create anything, can he create a rock that he himself cannot lift?" kind of deal - a meaningless philosophical debate because the parameters were constructed to make the problem possible in the first place. An "intellectual trap", if you will.
Alternatively: We know that the earth is not perfectly flat, so why are our spherical cows not rolling off the meadow?
function HALT(program, input):
# This is a "magic" function for our proof - we assume it exists for all programs
# In reality, this function cannot exist because of the paradox we're about to create
# Returns True if `program(input)` halts, False if it runs forever
...
# Program D: Creates the paradox
function D(self):
if HALT(D, self) == True:
loop_forever()
else:
halt()
The following argument from the blog post is wrong:
"First, write a bash script P1 that runs a SAT solver on every possible SAT problem and halts if any of them take exponential time. You don't actually have to run P1, just call HALTS(P1, Solver) to see if the solver solves all problems in polynomial time."
The difficulty here is that it could turn out that there's a SAT algorithm that is better than exponential, but the SAT solver used in the experiment does have worst case exponential time. What has to be proved, to prove P != NP, is that there is no possible SAT algorithm that has sub-exponential worst case time.
Is it me, or does the section about the Goldbach conjecture have nothing to do with the halting problem, but with finite machines?
As TFA points out, the program to solve the Goldbach Conjecture will halt, and we know this. Because it halts, it doesn't solve the conjecture (unless it does solve it within the range of numbers allowed by the finite system memory).
So it's got nothing to do with the halting conjecture - we know this program will definitely halt, because we don't have infinite memory. It also doesn't solve the conjecture, because it will halt. This seems like circular reasoning.
If we had an infinite machine then we could write a program that could solve the conjecture, if we had infinite time to run it in (or it ran infinitely fast). Because we don't have any of those things, writing a program to solve the conjecture is impossible, regardless of our ability to determine if it halted or not.
If we had the ability to determine if that program halted, we would still need an infinite machine to run the program, which we don't, so the ability to determine whether the program halts or not is irrelevant. We can't create such a program (because we can trivially determine that any such program will actually halt - yes it does, because it runs out of memory).
> So it's got nothing to do with the halting conjecture - we know this program will definitely halt, because we don't have infinite memory. It also doesn't solve the conjecture, because it will halt. This seems like circular reasoning.
Nothing circular there. The point is that "does this program halt on a computer of size xyz?" is a very uninteresting question (as you say, it will) whereas "does it halt on an infinite computer?" is a much more interesting question (because it's equivalent to the Goldbach conjecture). So the halting problem really is deep and interesting, in a way that the "finite halting problem" isn't.
> Yeah I get that, but if we're inventing magic infinite computers, why not invent magic halting algorithms?
Do you object to doing geometry because it involves a magic infinite plane? The point is that by studying the behaviour of this simple model we can learn useful things.
> This paragraph is essentially saying this - if we had magic computers then we could magic things we them, but we don't so we can't.
If you knew what a program would do on a magic computer, you could do very interesting things. The point isn't to have an actual magic computer.
The second version that only goes up to a certain number shows nothing, but that's on purpose, to show that a basic 'finite computer' limit throws out the interesting part of the problem.
The first version of the program has nothing wrong with it. If we had an infinity computer, we could run that exact program and get the answer.
We don't need an infinity computer to write the program.
If we had a halting tester that runs on a normal computer, we could feed it the program and then we would have the answer to the conjecture, without needing an infinity computer.
Stephen Wolfram talks about computational irreducibility and I think of that as essentially the same as the halting problem. I like his description that science advances by finding problems that we care about that are also computationally reducible. An equivalent with halting is to find those problems that we care about where halting can be proven (or disproven).
If the halting problem were decidable, we wouldn't need to rewrite the world in Rust; we could write a checker for C that would anticipate all memory safety violations of an arbitrary C program at compile time.
> we could write a checker for C that would anticipate all memory safety violations of an arbitrary C program at compile time.
I think that's called a "memory safe compiler". There have been multiple examples (SoftBoundCETS[1], Safe-C, Fail-Safe C, etc.) as well as partial/incremental solutions (-fbounds-safety, CheckedC, etc.)
An irritating problem with C is that it is underspecified, so many "working" C programs rely on unsafe operations that would be flagged as errors by a memory safe compiler.
The problem is with defining what a “memory safety violation” is. By the time you’ve annotated all the code with the information necessary to tell what you find undesirable up to rust’s capacity (e.g. overstepping buffers, violations of move semantics…), say through a type system that allows you to express these requirements, and have spent the time to change the parts of the program that did not fit with your new more restrictive types…
… well congratulations, you’ve just written your program in a language that effectively is rust.
The reason why the halting problem is of minor importance for pragmatically minded programmers has nothing to do with machine memory size. It's of minor importance because while it's intractably hard to prove an arbitrary program has some desired properties, it's considerably and practically easier to reliably construct a program with said properties. That problem of program construction is what we as programmers are trained and paid to do, and overall we do an adequate job of it.
You're missing the point of the article. It's showing that if the halting problem was decidable, lots of other things would also be possible (such as trivially proving various mathematical conjectures). It really has nothing much to do with what programmers do for their day job.
> ... because computers aren't Turing machines and have finite memory, so all programs are guaranteed to halt.
Is this simply wrong or am I not understanding? With finite memory, the halting problem is solvable, but that's different than all programs halt.
The program doesn't halt even with finite memory. Unless he means eventually the world will end, or the power supply will die, etc.> If the halting problem was solvable, then anyone with a computer could prove Goldbach's conjecture in an afternoon.
Why does he say "in an afternoon"? Maybe it would take 10^100 years? The halting problem be solvable or unsolvable is not a question of complexity or efficiency.
Yeah, I stumbled over that too. I think they meant to say any “interesting” program would halt. Programs that don’t halt will repeat state (in your example there isn’t even any state, so it’s trivially always the same), and the article wants to look at programs where we run out of state (and also describes why it isn’t interesting to halt when hitting the state size limit).
The gist of the article is of course correct, but it uses some terminology wrong. "Recursively enumerable" and "decidable" aren't applicable to instances of individual programs. In fact, every single instance of a problem is "decidable" because either the program that always returns true or the one that always returns false solves it (we don't necessarily know which one, but that isn't required). And in any case, for the Goldbach conjecture, the set of numbers that satisfy it is decidable - the function sum_of_two_primes is such a decision procedure.
What's undecidable is the set of valid conclusions (from some axioms) in first-order logic (in short, "FOL is undecidable"). So there is no algorithm that can tell us whether a given mathematical statement (including Goldbach's conjecture) is "true" (i.e. follows from the axioms of arithmetic, or ZFC, or something). FOL is recursively enumerable, since we can just generate all possible proofs.
Similarly, the set of halting programs isn't decidable, but it is recursively enumerable (every halting program halts at some time t, now enumerate all pairs (program, t) via a diagonal argument and check if program halts within t steps).
Someone discovered the halting problem again. Sigh.
First, the halting problem only applies to systems with infinite memory. If memory is finite and the system is deterministic, the program will either halt or repeat a state. The halting problem is thus decidable for non-infinite systems. So there.
The next question is whether there are programs with lower time bounds that can be made arbitrarily large. Actually, we don't know the answer to that. Cryptography assumes the answer is yes, but that's an assumption. We don't actually know that factoring is inherently hard, only that enough people have beaten on the problem that we know there's no easy to find shortcut.
Proof of correctness systems run into the complexity problem. You can write things that force a SAT solver to explore so many cases that it won't finish in any reasonable time. But that's not undecidability. My usual comment on this is that if your program is unreasonably hard to test for termination, it's broken. Microsoft takes that position with their Static Driver Verifier. There's a timeout; if it takes too long to prove your kernel driver safe, it doesn't get signed for use in the kernel.
> A lot of people use the proof that the halting problem is undesirable to make some deep philosophical point
Penrose comes to mind. There are people who are desperate to prove that humans transcend computers in some fundamental way. We heard a lot more from that crowd before LLMs started writing better than some of their critics.
> First, the halting problem only applies to systems with infinite memory. If memory is finite and the system is deterministic, the program will either halt or repeat a state. The halting problem is thus decidable for non-infinite systems. So there.
The article mentions this fact specifically in about the third paragraph, and goes on to talk about why it's less relevant than it might appear.
> The next question is whether there are programs with lower time bounds that can be made arbitrarily large. Actually, we don't know the answer to that.
No, the time hierarchy theorems prove that such programs exist.
> My usual comment on this is that if your program is unreasonably hard to test for termination, it's broken. Microsoft takes that position with their Static Driver Verifier. There's a timeout; if it takes too long to prove your kernel driver safe, it doesn't get signed for use in the kernel.
Timeouts make it much harder to reason about programs and perform safe refactors, because the class of refactors that are guaranteed to not break a program becomes quite small. E.g. you can no longer prove that "val y = f(x); g(y)" is correct if "g(f(x))" is correct and vice versa.
> The next question is whether there are programs with lower time bounds that can be made arbitrarily large. Actually, we don't know the answer to that. Cryptography assumes the answer is yes, but that's an assumption.
Cryptography does not assume that. It only needs a certain amount of slowness, and a large polynomial like n^20 is more than sufficient. But more importantly the best case for cryptographic security is exponential time. Cryptography ignores the entire science of super large numbers.
To really boil down what cryptography needs, it's problems that take ≤2^40 operations to verify but ≥2^200 (irreversible) operations to solve. It doesn't actually need to scale at all.
Also it's not hard to make programs that take huge amounts of time. In particular, a program that uses exponential time and leaves an exponentially long output is downright trivial to write. In pseudocode: while(i++ < 2^n) output.append(1)
> If memory is finite and the system is deterministic, the program will either halt or repeat a state. The halting problem is thus decidable for non-infinite systems.
While this is theoretically correct, there are offensively short programs for which we can't (yet) decide if they terminate or loop infinitely. E.g. Collatz conjecture offers such a program that does not even require a colossal state to track during execution, its state is one integer.
Sadly there are problems that are theoretically decidable but cannot be practically decidable, because the required computation would take the resources of the entire universe, and would take longer than it's projected to exist (at least in a state that can support computation).
[1]: https://en.wikipedia.org/wiki/Collatz_conjecture
> E.g. Collatz conjecture offers such a program that does not even require a colossal state to track during execution, its state is one integer.
Hence exactly as large as an infinite array of integers!
https://en.wikipedia.org/wiki/G%C3%B6del_numbering#G%C3%B6de...
Though I have the same intuition that the Collatz state doesn't feel large or complicated. It isn't updated, or used, in any complex way.
>The halting problem is thus decidable for non-infinite systems. So there.
The word "decidable" invokes a computer with infinite memory.
This is a rant I’ve had in my head forever, so thanks for posting this. A lot of people use the proof that the halting problem is undesirable to make some deep philosophical point, like this one. But the actual proof is so disappointing and non-philosophical that I wonder if anyone making these grand statements has ever read it. It just invents a program which outwits the halting detector by doing the opposite of what it would otherwise say.
Its like, if you met the smartest person in the world, and you asked them “will you answer no to this question” and then no matter what they said you laughed in their face and said hah, guess you’re not so smart, are you?
And THAT is why you think we don’t live in heaven?
Like, OP says that because of this proof we can’t run HALT() on a program that assets the Goldbach conjecture. What? That’s entirely orthogonal from the proof of the undecidability of the halting program, unless one of the primes has embedded a trick logic question into itself somehow. There’s nothing stopping there from being a “HALT_FOR_EVERY_PROGRAM_EVER_EXCEPT_THAT_ONE_TRICK_PROGRAM”. There you go, you’re back in heaven again!
Kolmogorov complexity is undecidable because the halting problem is undecidable. If we could solve Kolmogorov complexity we could do Solomonoff induction and build AIXI and solve (at least one formulation of) decision theory.
The real problem (imo) is that proof search is also undecidable (either directly from halting problem or similar argument) and so there isn't a procedure we can write that identifies trick programs to exclude as special cases. There are an infinite number of various trick programs for which halting is undecidable and recognizing them is undecidable.
> There’s nothing stopping there from being a “HALT_FOR_EVERY_PROGRAM_EVER_EXCEPT_THAT_ONE_TRICK_PROGRAM”.
Doesn't work that way. If we have "HALT_FOR_...EXCEPT_THAT_ONE_TRICK_PROGRAM", then we can simply create "HALT_FOR_ACTUALLY_EVERY_PROGRAM" by:
...but this is impossible, because then it would actually solve the full halting program, and we know it's impossible.So the best you can have is "Solve the halting problem for a bunch of programs, but not for a bunch of others, but that's okay because will call the latter as 'trick programs.'"
And the problem is that you can't give a mathematically satisfying definition of what is a trick program, and whatever you try, you'll likely end up defining a lot of actually interesting programs as trick programs. So it's actually "Solve the halting problem for some programs, but not others." And that's not terribly interesting, because we already know it's possible.
I am probably not the only one who finds the above as pointless as trying to determine whether the sentence "this sentence is false" is true or false. It is neither, but most of the time we're interested in problems that have answers, and that problem space turns out to be huge and extremely useful.
What are some good examples of practical programs that aren't trying to create a chain of computation that is ultimately circular and self-referential yet still run into trouble with the halting problem?
> What are some good examples of practical programs that aren't trying to create a chain of computation that is ultimately circular and self-referential yet still run into trouble with the halting problem?
Almost any unproven mathematical conjecture, e.g. a program that searches for counterexamples to the Riemann hypothesis. More practically, a lot of problems reduce to SAT, so these days quite a lot of systems work by just running a SAT solver on the problem (e.g. dependency resolution in some build systems), and it's fast most of the time but you can never be sure it's not going to get stuck.
> Almost any unproven mathematical conjecture, e.g. a program that searches for counterexamples to the Riemann hypothesis.
This is a very good example. We don't know whether such programs will ever stop, and knowing is exactly equivalent to resolving the conjectures.
> More practically, a lot of problems reduce to SAT, so these days quite a lot of systems work by just running a SAT solver on the problem (e.g. dependency resolution in some build systems), and it's fast most of the time but you can never be sure it's not going to get stuck.
This is a less good example because SAT solvers can always run in finite time and can be proven to halt. Even if they do "get stuck", they will take exponential time rather than infinite time.
There are probably some problems that arise practically that are undecidable in general (e.g. type checking for sufficiently expressive type systems), but problems that "reduce to SAT" are never examples of such undecidable problems because SAT is decidable.
I was going to say the same thing about SAT, or any NP-hard problem.
The first example doesn't seem to be good either however. I don't think that proving a mathematical conjecture which has resisted proof for decades (or longer) is something that we would typically expect a computer program to be able to do. Whenever this happens, it is hailed as a major breakthrough.
The point is that it can complicate analysis of a program, at least if you take the fundamentalist view that all program behaviour should be provably correct. Like if you need the collantz sequence of a number or something in your program, you would just calculate it and use it, but it's surprisingly hard to prove that it always exists. Which isn't so much a problem in itself as it complicates trying to prove anything else about your program's behaviour.
Is there some circular logic in your reasoning? What is the difference between the computer program solving the conjecture, and “us” doing it?
> So the best you can have is "Solve the halting problem for a bunch of programs, but not for a bunch of others, but that's okay because will call the latter as 'trick programs.'"
The awesome and surprising thing is, I’ve actually written such a program! It regularly runs the program to test, but stops and screams “trick program!” if the program to test did not finish within five minutes. Sadly, I haven’t been awarded my Fields Medal yet, probably because I didn’t use LLMs.
The philosophical issue is there are questions which seem "simple" and have answers, but even if given the answer you could not know whether it was the right answer.
The halting problem is more than that. While the proof constructs a relatively trivial Turing machine that basically puts the toddler's "Nuh-uh!" on solid mathematical ground, that's just the proof that there exists at least one Turing machine for a given halting oracle that can not be predicted by that halting oracle.
To get to where you're complaining about people going, it needs to be paired with Rice's Theorem, as mentioned in the article: https://en.wikipedia.org/wiki/Rice%27s_theorem
It is true that the halting problem itself is perhaps not directly what people seem to think it is, but people turn out to be right anyhow, because Rice's Theorem can be largely summed up as "It can be proven that we can not have nice things", if you'll allow me a bit of mathematician-style humor, which corresponds more-or-less to the way people talk about the Halting Problem.
This also explains why the Goldbach conjecture is in fact directly related to the halting problem and not orthogonal at all. Through Rice's theorem we can extend the halting problem quite easily to the solution to that and a lot of other problems.
By computer science standards, Rice's theorem is relatively basic stuff. I don't recall if the sophomore-level class I learned about this stuff did a full proof of Rice's theorem but I certainly recall several homework problems around applying the idea of the theorem to several specific problems by proving reductions of those problems to the halting problem. I also recall they really weren't particularly difficult problems. It's not hard to reduce that sort of interesting question to the halting problem. Low-level undergrad stuff, stuff down in the very basics of computer science qua computer science suitable for making up several problems in the weekly homework assignment for the intro to (real) computer science course, not complicated abtruse stuff that can't be applied by anyone less than a doctoral candidate with a few months to burn. All sorts of problems are reducible like this.
And that is why the "halting problem" in fact is the reason why we can't have certain nice things we'd really like. For example, the mentioned ability to prove that two functions really are equivalent would have practical utility in a wide variety of places (assuming somewhat reasonable efficiency), like compiler optimizations.
Your intuition is correct in one respect though; there is a sense in which it isn't really "The Halting Problem (TM)". You could take a wide variety of other problems and call them "the" fundamental problem, and reduce the halting problem to those problems. The Halting Problem just turns out to be a particularly concise specific expression of the general problem that is easy to express for Turing Machines. It just makes for nicer proofs than the alternatives. "The" core problem could arguably be something more like Rice's Theorem proved on its own as a fundamental proof without reference to the halting problem. You could call the Halting Problem a historical accident that we hold on to due to a path dependency in how math happened to develop in our history. An alien race might have a reasonably different view on the "fundamental problem", but then they'd have a something fairly similar to Rice's Theorem sitting on top of it that we'd all recognize.
Yeah, it's fundamentally a "if god can create anything, can he create a rock that he himself cannot lift?" kind of deal - a meaningless philosophical debate because the parameters were constructed to make the problem possible in the first place. An "intellectual trap", if you will.
Alternatively: We know that the earth is not perfectly flat, so why are our spherical cows not rolling off the meadow?
Your comment helped me get this:
The following argument from the blog post is wrong:
"First, write a bash script P1 that runs a SAT solver on every possible SAT problem and halts if any of them take exponential time. You don't actually have to run P1, just call HALTS(P1, Solver) to see if the solver solves all problems in polynomial time."
The difficulty here is that it could turn out that there's a SAT algorithm that is better than exponential, but the SAT solver used in the experiment does have worst case exponential time. What has to be proved, to prove P != NP, is that there is no possible SAT algorithm that has sub-exponential worst case time.
That’s why there is the second program P2 which runs P1 on all possible solvers and checks if any of them succeeds.
Is it me, or does the section about the Goldbach conjecture have nothing to do with the halting problem, but with finite machines?
As TFA points out, the program to solve the Goldbach Conjecture will halt, and we know this. Because it halts, it doesn't solve the conjecture (unless it does solve it within the range of numbers allowed by the finite system memory).
So it's got nothing to do with the halting conjecture - we know this program will definitely halt, because we don't have infinite memory. It also doesn't solve the conjecture, because it will halt. This seems like circular reasoning.
If we had an infinite machine then we could write a program that could solve the conjecture, if we had infinite time to run it in (or it ran infinitely fast). Because we don't have any of those things, writing a program to solve the conjecture is impossible, regardless of our ability to determine if it halted or not.
If we had the ability to determine if that program halted, we would still need an infinite machine to run the program, which we don't, so the ability to determine whether the program halts or not is irrelevant. We can't create such a program (because we can trivially determine that any such program will actually halt - yes it does, because it runs out of memory).
> So it's got nothing to do with the halting conjecture - we know this program will definitely halt, because we don't have infinite memory. It also doesn't solve the conjecture, because it will halt. This seems like circular reasoning.
Nothing circular there. The point is that "does this program halt on a computer of size xyz?" is a very uninteresting question (as you say, it will) whereas "does it halt on an infinite computer?" is a much more interesting question (because it's equivalent to the Goldbach conjecture). So the halting problem really is deep and interesting, in a way that the "finite halting problem" isn't.
Yeah I get that, but if we're inventing magic infinite computers, why not invent magic halting algorithms?
> the halting problem was solvable, then anyone with a computer could prove Goldbach's conjecture in an afternoon.
This paragraph is essentially saying this - if we had magic computers then we could magic things we them, but we don't so we can't.
> Yeah I get that, but if we're inventing magic infinite computers, why not invent magic halting algorithms?
Do you object to doing geometry because it involves a magic infinite plane? The point is that by studying the behaviour of this simple model we can learn useful things.
> This paragraph is essentially saying this - if we had magic computers then we could magic things we them, but we don't so we can't.
If you knew what a program would do on a magic computer, you could do very interesting things. The point isn't to have an actual magic computer.
The second version that only goes up to a certain number shows nothing, but that's on purpose, to show that a basic 'finite computer' limit throws out the interesting part of the problem.
The first version of the program has nothing wrong with it. If we had an infinity computer, we could run that exact program and get the answer.
We don't need an infinity computer to write the program.
If we had a halting tester that runs on a normal computer, we could feed it the program and then we would have the answer to the conjecture, without needing an infinity computer.
Stephen Wolfram talks about computational irreducibility and I think of that as essentially the same as the halting problem. I like his description that science advances by finding problems that we care about that are also computationally reducible. An equivalent with halting is to find those problems that we care about where halting can be proven (or disproven).
One past discussion:
https://news.ycombinator.com/item?id=37204624 - 26 points by azhenley on Aug 21, 2023, 21 comments
If the halting problem were decidable, we wouldn't need to rewrite the world in Rust; we could write a checker for C that would anticipate all memory safety violations of an arbitrary C program at compile time.
> we could write a checker for C that would anticipate all memory safety violations of an arbitrary C program at compile time.
I think that's called a "memory safe compiler". There have been multiple examples (SoftBoundCETS[1], Safe-C, Fail-Safe C, etc.) as well as partial/incremental solutions (-fbounds-safety, CheckedC, etc.)
An irritating problem with C is that it is underspecified, so many "working" C programs rely on unsafe operations that would be flagged as errors by a memory safe compiler.
[1] "Full Spatial and Temporal Memory Safety for C", https://people.cs.rutgers.edu/~sn349/papers/safety-sp-2024.p...
The problem is with defining what a “memory safety violation” is. By the time you’ve annotated all the code with the information necessary to tell what you find undesirable up to rust’s capacity (e.g. overstepping buffers, violations of move semantics…), say through a type system that allows you to express these requirements, and have spent the time to change the parts of the program that did not fit with your new more restrictive types…
… well congratulations, you’ve just written your program in a language that effectively is rust.
This article is attacking a straw man.
The reason why the halting problem is of minor importance for pragmatically minded programmers has nothing to do with machine memory size. It's of minor importance because while it's intractably hard to prove an arbitrary program has some desired properties, it's considerably and practically easier to reliably construct a program with said properties. That problem of program construction is what we as programmers are trained and paid to do, and overall we do an adequate job of it.
You're missing the point of the article. It's showing that if the halting problem was decidable, lots of other things would also be possible (such as trivially proving various mathematical conjectures). It really has nothing much to do with what programmers do for their day job.