Misha comments on The Curve of Capability - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (264)
I suppose I wasn't precise enough. Actual researchers in that area are, rightly, interested in more-or-less reasonable halting questions. But these don't contradict our intuition about what halting problems are. In fact, I would guess that a large class of reasonable programming mistakes can be checked algorithmically.
But as far as consequences for there being, hypothetically, a solution to the general halting problem... the really significant result would be the existence of a general "problem solving algorithm". Sure, Turing's undecidability problem proves that the halting problem is undecidable... but this is my best attempt at capturing the intuition of why it's not even a little bit close to being decidable.
Of course, even in a world where we had a halting solver, we probably wouldn't want to use it to prove the Riemann Hypothesis. But your comment actually reminds me of a clever little problem I once saw. It went as follows:
(the connection to your comment is that even if P=NP, we wouldn't actually use the solution to the above problem in practical applications. We'd try our best to find something better)