3 ms·
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 wou
by ndsipa_pomu 3y ago
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.
- 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.