= 27d567bc2d48d9f40e9ccc20ea370b15)
tut comments on Open Thread - Aug 24 - Aug 30 - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (318)
It does not give a counterexample. It specifies a way that you could find a counterexample if there was a halting oracle. But if there was a halting oracle there wouldn't be any counterexample. So what is found is a contradiction.
The standard halting problem proof doesn't specify what the halting oracle is. It just shows how to construct a counter example for any halting oracle. I actually specified a halting oracle; a program which searches through all possible proofs until it finds a proof that it halts or not.
Then running it on the counterexample causes it to run forever. Therefore I've proved that it will run forever. The program will eventually find that proof, return false, and halt.
{All possible proofs} has infinitely many elements longer than zero, so your algorithm will (might) run forever on some programs that do halt, so it is not a halting oracle.
If a program halts, it's easy to prove that it halts. Just run it until it halts. The problem is proving that some programs won't halt.