Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com