Hacker News Reader

Comment by explaininjs | Hacker News Reader

P/NP and Halting are entirely different concepts. I suggest reading up on the Halting problem - it’s actually very mind opening.

Edit: it wouldn’t be a stretch to call it the most important result in all of mathematics

View on HN

If you have a solution to the halting problem, then it would be possible to cast the P/NP problems in terms of a program and knowing whether or not it halts would allow you to determine whether P=NP.

That may be, but statements that start “if false …” aren’t very useful.

The halting problem has been proven definitively undecidable via proof by contradiction, by Alan Turing. The proof implicitly created the notion of Turing machines, a key model of computation.

There is a solution to the halting problem. It’s that it is undecidable.

Yes. The Halting Problem is just Gõdel incompleteness in drag. They're both the same idea and they're both thoroughly proven.

I had originally written something to that effect, but recanted after I saw Turing claimed “what I shall prove is quite different from the well-known results of Gödel”. I’d need to sit down longer to determine how equivalent they really are.

Would love to see the reference for this. I expect he might be referring to the idea of executing an embodied algorithm on a machine, while Gödel was talking about pure math.

Page 27 here: https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2...

Reply on news.ycombinator.com