4 ms·

Godels incompleteness theorem and the Halting problem are very nearly equivalent. I believe Turing, very soon after hearing about Godels' incompleteness theorem

Godels incompleteness theorem and the Halting problem are very nearly equivalent. I believe Turing, very soon after hearing about Godels' incompleteness theorem, used it to show the non-existence of the Halting problem. The consequences of Godel's incompleteness theorem and the Halting problem wove into many outstanding problems, including Hilbert's 10th problem. I would argue that computation is a much more natural setting for thinking about these ideas. Whether is recursively enumerable sets, Diophantine equations or set theory doesn't fundamentally matter so much, as they're all equivalent in some way. I wouldn't argue that you, or anyone else, shouldn't think of it in that way, but in my opinion, for many people, myself included, casting it through a computational lens makes more sense. Not to harp on a small point but I would argue the diagonalization proof of the Halting problem relies on there being different orders of infinity, not that Z itself is infinite. Since Godel's incompleteness, we know that the continuum hypothesis can be true or false depending on which (consistent) axioms you choose, so I would argue that it's not so much which axioms we choose for how we think about infinities that's fundamental but the fact that consistent systems of sufficient complexity must be incomplete. I'm firmly in the P!=NP camp but I commend you for putting your beliefs out there and actually doing the work. I do believe people throw up their hands when they hear "NP-Complete" when they absolutely shouldn't. The path from problems being "easy" (polynomial) to "hard" (exponential) is not very well understood and even if a problem is, in general, NP-Complete doesn't mean that a particular ensemble of problems being drawn from couldn't be solved by some clever polynomial time algorithm. And of course, P ?= NP still remains an open problem so we still don't understand something pretty fundamental.

js8 3y ago
> Not to harp on a small point but I would argue the diagonalization proof of the Halting problem relies on there being different orders of infinity, not that Z itself is infinite. I am philosophically very close to finitism, and I think from the perspective of the Skolem's paradox it's not clear whether different infinities are not just a "mirage", so to speak. The distinction between finite and infinite seems to be much more "real" to me. > but the fact that consistent systems of sufficient complexity must be incomplete The problem is that if P!=NP, then it would seem to imply (from what I have seen) that there is a large class of finite deduction systems which are incomplete, no matter what rules of inference you pick. This to me is a lot more counterintuitive than simply accepting that finite and infinite are just very, very different worlds, and our intuition easily fails when we transfer results from one to another. And as I describe in that other thread, with the 2XSAT being NP-complete, the idea that you have two finite sets in Z_2^n that are each relatively easy to describe (instance of 2SAT and instance of XORSAT), but their intersection (which is in 2XSAT) is somehow "difficult" to describe is just.. really really hard to take seriously. Of course it's just another intuition, but I don't see how anybody who believes that P!=NP can look at this and not start doubting it. > I do believe people throw up their hands when they hear "NP-Complete" when they absolutely shouldn't. I very much agree. I was originally agnostic on whether P=NP (now I am tilted to believe that P=NP and there is actually an efficient algorithm). I always felt that assuming P=NP ("assuming" in the philosophical not mathematical sense) and looking for a polynomial algorithm (what would the polynomial algorithm have to look like, for example, it would have to represent exponential number of solutions to look at them at once) is a better way to progress on the question rather than assuming P!=NP. (Kinda like if we assume that the world is knowable, we are more motivated to know it, rather than if we assume it's unknowable.) It's also better in practice because if you actually try to construct a polynomial algorithm, and it fails, you will get a much more concrete idea what the obstacle is (a specific set of instances where it fails). I think because of the natural proofs, if you assume P!=NP, then you believe that progressing this way is essentially impossible. So I think that's the reason why people give up, because if you believe P!=NP, resolving it this way is hopeless, and at the same time, nobody has any better idea. However, if you ever so slightly believe that P=NP, and humans are just not smart enough to figure it out in 50 years (remember, it took several centuries to figure out Gaussian elimination, which seems completely obvious in retrospect), then you're not constrained with natural proof limitations and there is no reason for hopelessness.
- abetusk 3y ago
  > I am philosophically very close to finitism, and I think from the perspective of the Skolem's paradox it's not clear whether different infinities are not just a "mirage", so to speak. The distinction between finite and infinite seems to be much more "real" to me. I think I'm also in the same camp (finitism). My view is that infinities are kind of "verbs" rather than "nouns", even if we use them as if they were nouns for short-hand. I guess another way to say that is infinities have algorithms associated with them, where we kind of "turn the crank" and get more output. > And as I describe in that other thread, with the 2XSAT being NP-complete, the idea that you have two finite sets in Z_2^n that are each relatively easy to describe (instance of 2SAT and instance of XORSAT), but their intersection (which is in 2XSAT) is somehow "difficult" to describe is just.. really really hard to take seriously. Of course it's just another intuition, but I don't see how anybody who believes that P!=NP can look at this and not start doubting it. I don't understand the hesitation here. Once you have a fundamental gate (NOR, NAND, etc.) you have universal computation. In my opinion, 2-SAT is just barely in P because of the extraordinary restriction that each clause have 2 variables. As soon as you relax that condition, it's easy to do arbitrary computation. > ... if you assume P!=NP, then you believe that progressing this way is essentially impossible. I think we're in agreement here. My personal view is that it's not so much better to assume P=NP as it is to understand that there are different ensembles of problem space to choose from and even if the larger "space" is NP-Complete, the ensemble might only produce "almost sure" polynomial solvable instances. This is the case for Hamiltonian Cycle problems on Erdos-Renyi random graphs, for example. > ... then you're not constrained with natural proof limitations and there is no reason for hopelessness. I do wish I understood the natural proof limitation a bit better. I suspect there's a loophole somewhere or, at the very least, pointing us to another region of proof technique, but I just don't understand it well enough to know what's going on. > ... now I am tilted to believe that P=NP and there is actually an efficient algorithm ... I guess I don't have much hope of convincing you otherwise but I would like to point out again the "finite Halting Problem" interpretation. For an arbitrary program F(inp,K) (input `inp` and runs for K steps as a parameter), you're saying that the following can effectively be short circuited from an exponential search to a polynomial one: for inp in [0 .. 2^{n-1}] do if F(inp,K) then return true done return false To my eyes, if this can be short-circuited, it's essentially saying that for arbitrary functions, there's no actual reason to do computation as it can be short-circuited. In other words, you're saying one can do better than raw simulation in every single case. While potentially true, it seems like a pretty bold statement.

js8 3y ago

> Not to harp on a small point but I would argue the diagonalization proof of the Halting problem relies on there being different orders of infinity, not that Z itself is infinite. I am philosophically very close to finitism, and I think from the perspective of the Skolem's paradox it's not clear whether different infinities are not just a "mirage", so to speak. The distinction between finite and infinite seems to be much more "real" to me. > but the fact that consistent systems of sufficient complexity must be incomplete The problem is that if P!=NP, then it would seem to imply (from what I have seen) that there is a large class of finite deduction systems which are incomplete, no matter what rules of inference you pick. This to me is a lot more counterintuitive than simply accepting that finite and infinite are just very, very different worlds, and our intuition easily fails when we transfer results from one to another. And as I describe in that other thread, with the 2XSAT being NP-complete, the idea that you have two finite sets in Z_2^n that are each relatively easy to describe (instance of 2SAT and instance of XORSAT), but their intersection (which is in 2XSAT) is somehow "difficult" to describe is just.. really really hard to take seriously. Of course it's just another intuition, but I don't see how anybody who believes that P!=NP can look at this and not start doubting it. > I do believe people throw up their hands when they hear "NP-Complete" when they absolutely shouldn't. I very much agree. I was originally agnostic on whether P=NP (now I am tilted to believe that P=NP and there is actually an efficient algorithm). I always felt that assuming P=NP ("assuming" in the philosophical not mathematical sense) and looking for a polynomial algorithm (what would the polynomial algorithm have to look like, for example, it would have to represent exponential number of solutions to look at them at once) is a better way to progress on the question rather than assuming P!=NP. (Kinda like if we assume that the world is knowable, we are more motivated to know it, rather than if we assume it's unknowable.) It's also better in practice because if you actually try to construct a polynomial algorithm, and it fails, you will get a much more concrete idea what the obstacle is (a specific set of instances where it fails). I think because of the natural proofs, if you assume P!=NP, then you believe that progressing this way is essentially impossible. So I think that's the reason why people give up, because if you believe P!=NP, resolving it this way is hopeless, and at the same time, nobody has any better idea. However, if you ever so slightly believe that P=NP, and humans are just not smart enough to figure it out in 50 years (remember, it took several centuries to figure out Gaussian elimination, which seems completely obvious in retrospect), then you're not constrained with natural proof limitations and there is no reason for hopelessness.

abetusk 3y ago
> I am philosophically very close to finitism, and I think from the perspective of the Skolem's paradox it's not clear whether different infinities are not just a "mirage", so to speak. The distinction between finite and infinite seems to be much more "real" to me. I think I'm also in the same camp (finitism). My view is that infinities are kind of "verbs" rather than "nouns", even if we use them as if they were nouns for short-hand. I guess another way to say that is infinities have algorithms associated with them, where we kind of "turn the crank" and get more output. > And as I describe in that other thread, with the 2XSAT being NP-complete, the idea that you have two finite sets in Z_2^n that are each relatively easy to describe (instance of 2SAT and instance of XORSAT), but their intersection (which is in 2XSAT) is somehow "difficult" to describe is just.. really really hard to take seriously. Of course it's just another intuition, but I don't see how anybody who believes that P!=NP can look at this and not start doubting it. I don't understand the hesitation here. Once you have a fundamental gate (NOR, NAND, etc.) you have universal computation. In my opinion, 2-SAT is just barely in P because of the extraordinary restriction that each clause have 2 variables. As soon as you relax that condition, it's easy to do arbitrary computation. > ... if you assume P!=NP, then you believe that progressing this way is essentially impossible. I think we're in agreement here. My personal view is that it's not so much better to assume P=NP as it is to understand that there are different ensembles of problem space to choose from and even if the larger "space" is NP-Complete, the ensemble might only produce "almost sure" polynomial solvable instances. This is the case for Hamiltonian Cycle problems on Erdos-Renyi random graphs, for example. > ... then you're not constrained with natural proof limitations and there is no reason for hopelessness. I do wish I understood the natural proof limitation a bit better. I suspect there's a loophole somewhere or, at the very least, pointing us to another region of proof technique, but I just don't understand it well enough to know what's going on. > ... now I am tilted to believe that P=NP and there is actually an efficient algorithm ... I guess I don't have much hope of convincing you otherwise but I would like to point out again the "finite Halting Problem" interpretation. For an arbitrary program F(inp,K) (input `inp` and runs for K steps as a parameter), you're saying that the following can effectively be short circuited from an exponential search to a polynomial one: for inp in [0 .. 2^{n-1}] do if F(inp,K) then return true done return false To my eyes, if this can be short-circuited, it's essentially saying that for arbitrary functions, there's no actual reason to do computation as it can be short-circuited. In other words, you're saying one can do better than raw simulation in every single case. While potentially true, it seems like a pretty bold statement.