3 ms·
Turing kicked us out of Heaven (2023)
- labster 2y ago[flagged]
- Jtsummers 2y agoOne past discussion: https://news.ycombinator.com/item?id=37204624 https://news.ycombinator.com/item?id=37204624 - 26 points by azhenley on Aug 21, 2023, 21 comments
- bitwize 2y agoIf 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.
- musicale 2y ago> 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.pdf https://people.cs.rutgers.edu/~sn349/papers/safety-sp-2024.p...
- musicale 2y agoFollowing up I note that you said "at compile time". Usually C programs have data-dependent behavior, which necessitates runtime checks (but generating those checks is an example of "anticipating memory safety violations.") Symbolic execution can potentially identify possible data-dependent memory safety violations, and it has been used in compilers and code checkers, but it can also become intractable (algorithm may be decidable, but the compute and memory requirements may be too high.)
- anyfoo 2y agoThe 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.
- jebarker 2y agoStephen 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).
- not2b 2y agoThe 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.
- xigoi 2y agoThat’s why there is the second program P2 which runs P1 on all possible solvers and checks if any of them succeeds.
- johnfn 2y agoThis 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!
- jerf 2y agoThe 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 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.
- Animats 2y agoSomeone 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.
- AlotOfReading 2y agoThe 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.
- Dylan16807 2y ago> 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)
- marcus_holmes 2y agoIs 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).
- Dylan16807 2y agoThe 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.
- lmm 2y ago> 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.
- ks2048 2y ago> ... 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.
- anyfoo 2y agoYeah, 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).
- User23 2y agoThis 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.
- MattPalmer1086 2y agoYou'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.
- Tainnor 2y agoThe 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).