3 ms·
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
by explaininjs 3y ago
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
- ndsipa_pomu 3y agoIf 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.
- explaininjs 3y agoThat may be, but statements that start “if false …” aren’t very useful.
- sharkbot 3y agoThe 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.
- dreamcompiler 3y agoYes. The Halting Problem is just Gõdel incompleteness in drag. They're both the same idea and they're both thoroughly proven.
- explaininjs 3y agoI 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.
- dreamcompiler 3y agoWould 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.
- explaininjs 3y agoPage 27 here: https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2...