17 ms·

every time i read about theoretical cs I’m left with multiple questions: How can we justify not steelmanning a ternary approach to halting? Can someone show me

every time i read about theoretical cs I’m left with multiple questions: How can we justify not steelmanning a ternary approach to halting? Can someone show me one proof which doesn’t rely on “muh do the opposite” (how do we know the halts program can’t detect this and crash with Err(ParadoxError)?) or the circular logic appeal to Rice’s theorem which itself depends on halts being undecidable? I’ve yet to find one. Collatz Conjecture? Only with unbounded memory and time, which is un-physical. That’s something we learned from Ray Solomonoff: the difference between doable and impossible is often a time limit. According to the concept of equivalence, aren’t p and np both equivalent and not, in infinite ways (a “filibuster proof,” just make the argument for and against their equivalence based on their mutual relationship to each counting number), and fundamentally designed to be not equal by virtue of us naming them differently? Finally, what the heck was Gödel thinking to assume we can assign different numbers to zero and the logical not? If the Gödel numbers are off, or even if not, how can an incompleteness theorem be complete? And if the incompleteness theorem is itself incomplete, why should we take it super seriously? Just seems like we take the validity of these fundamentals for granted, and “most computer scientists believe X” is not exactly a strong argument for anyone to believe X, because it’s an appeal to mass belief. Lest anyone think I’m a snooty smarty pants, I’d like to say i think I’m an idiot. Every day i beat myself up for being an idiot. Go ahead and feel free to downvote for this, or call me a crackpot, but a bunch of bedrock ideas of theoretical cs really are weird and suspect - decision problems with Boolean outputs are inherently nerfed compared to ternary ones with options to refuse to answer or to stop programs from outside - p vs np suffers the same problem, since “equals” or “not equals” ignores the infinitely huge elephant of “equivalence” (not equal how?) - Gödel numbering zero (an integer) and logical not (a function) separately is a false difference because zero IS not (to the universe itself) — to say we can’t form complete systems out of items we ourselves falsely separated in the first place is what the universal substrate, if it could speak, might call a “skill issue”

kaba0 2y ago
> How can we justify not steelmanning a ternary approach to halting? Can someone show me one proof which doesn’t rely on “muh do the opposite I don’t even understand what you are getting at. But humbling ourselves and learning new things, especially such influential thoughts that mathematical giants such as Gödel and Turing gifted us with (and were since refined by hundreds of very smart people) should be the first step. All these thoughts were refined over a century, or half. It’s not some proposition that sounds cool and might later be proven wrong. A Turing machine is fantastically simple and the halting problem is well-defined over it — it has n states, and one of them is labeled as HALT. Does it ever get to this state? There is no ternary option here. (Note: Turing didn’t even consider them halting, but used an equivalent problem)
jcranmer 2y ago
The joys of responding to someone who is so confused about terminology that you have trouble even figuring out what they meant to so... > How can we justify not steelmanning a ternary approach to halting? I'm not certain I understand what you mean here. In actual practice, the usual approach to undecidable problems--which come up all the time in compilers and formal methods, mind you--is to build a trichotomy of "yes", "no", and "don't know" (sometimes expressed "timeout"). What undecidability says is we can't squeeze the "don't know" category down to nothing, but in many circumstances, that's just fine. > Can someone show me one proof which doesn’t rely on “muh do the opposite” (how do we know the halts program can’t detect this and crash with Err(ParadoxError)?) or the circular logic appeal to Rice’s theorem which itself depends on halts being undecidable? Depending on how you define "muh do the opposite", this may be impossible. The essential crux of the theorem is that once your system reaches a certain level of power, it admits the possibilities of quines, which enables a level of self-reference that leads to paradoxes. The best attempt I can give, that only indirectly reaches into self-reference is this: Let f(x) be a program that returns the size of the smallest size program needed to output x (this is called Kolmogrov complexity). Let h(p) be a program that returns whether or not the input program p will halt. If h(p) exists, then f(x) necessarily exists: for p = 1 to infinity: if h(p) is true: if p computes x: return sizeof(p) If f(x) exists, we can write g(y) (informally, output the smallest integer that has at least a given Kolmogrov complexity) as follows: for x = 1 to infinity: if f(x) > y: return x However, we have a paradox now. If g exists, it has a size, which of course bounds the maximum complexity of its output. But we've just asserted that the output has to have a minimum complexity--and if we choose the bounds right, there's no possible overlap. Consequently, something in the construction must be wrong. Yet I've given the code for every program but the halting program... which means the halting program itself can't exist.
- lo0dot0 2y ago
  I don't understand your proof. It would make more sense to me if I add the additional idea that there is some p* where p* = h , where p* is part of p = 1 to infinity. So you have tried to define the halting program, but this led to a contradiction.
  - 2y ago
samatman 2y ago
Paul Graham just published an article about the difference between obstinacy and persistence, which might help you out here. https://news.ycombinator.com/item?id=40907155 https://news.ycombinator.com/item?id=40907155

kaba0 2y ago

> How can we justify not steelmanning a ternary approach to halting? Can someone show me one proof which doesn’t rely on “muh do the opposite I don’t even understand what you are getting at. But humbling ourselves and learning new things, especially such influential thoughts that mathematical giants such as Gödel and Turing gifted us with (and were since refined by hundreds of very smart people) should be the first step. All these thoughts were refined over a century, or half. It’s not some proposition that sounds cool and might later be proven wrong. A Turing machine is fantastically simple and the halting problem is well-defined over it — it has n states, and one of them is labeled as HALT. Does it ever get to this state? There is no ternary option here. (Note: Turing didn’t even consider them halting, but used an equivalent problem)

jcranmer 2y ago

The joys of responding to someone who is so confused about terminology that you have trouble even figuring out what they meant to so... > How can we justify not steelmanning a ternary approach to halting? I'm not certain I understand what you mean here. In actual practice, the usual approach to undecidable problems--which come up all the time in compilers and formal methods, mind you--is to build a trichotomy of "yes", "no", and "don't know" (sometimes expressed "timeout"). What undecidability says is we can't squeeze the "don't know" category down to nothing, but in many circumstances, that's just fine. > Can someone show me one proof which doesn’t rely on “muh do the opposite” (how do we know the halts program can’t detect this and crash with Err(ParadoxError)?) or the circular logic appeal to Rice’s theorem which itself depends on halts being undecidable? Depending on how you define "muh do the opposite", this may be impossible. The essential crux of the theorem is that once your system reaches a certain level of power, it admits the possibilities of quines, which enables a level of self-reference that leads to paradoxes. The best attempt I can give, that only indirectly reaches into self-reference is this: Let f(x) be a program that returns the size of the smallest size program needed to output x (this is called Kolmogrov complexity). Let h(p) be a program that returns whether or not the input program p will halt. If h(p) exists, then f(x) necessarily exists: for p = 1 to infinity: if h(p) is true: if p computes x: return sizeof(p) If f(x) exists, we can write g(y) (informally, output the smallest integer that has at least a given Kolmogrov complexity) as follows: for x = 1 to infinity: if f(x) > y: return x However, we have a paradox now. If g exists, it has a size, which of course bounds the maximum complexity of its output. But we've just asserted that the output has to have a minimum complexity--and if we choose the bounds right, there's no possible overlap. Consequently, something in the construction must be wrong. Yet I've given the code for every program but the halting program... which means the halting program itself can't exist.

lo0dot0 2y ago
I don't understand your proof. It would make more sense to me if I add the additional idea that there is some p* where p* = h , where p* is part of p = 1 to infinity. So you have tried to define the halting program, but this led to a contradiction.
- 2y ago

samatman 2y ago

Paul Graham just published an article about the difference between obstinacy and persistence, which might help you out here. https://news.ycombinator.com/item?id=40907155 https://news.ycombinator.com/item?id=40907155