= 27d567bc2d48d9f40e9ccc20ea370b15)
Dagon 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)
Nope, it also can't be proven that it'll search forever: it might halt a few billion years (or a few hundred ms) in. There's no period of time of searching after which you can say "it'll continue to run forever",as it might halt while you're saying it, which is embarrassing.
I am referring to the program
Hwhich I formally specified in the link I posted. H is a specific program which tries to determine if another program will halt.I then show how to create a counter example for
H. And show that ifHreturns eithertrueorfalse, it creates a contradiction. Therefore it can't ever returntrueorfalse.Therefore I've proved it will run forever. And this is just the standard proof of the halting problem. The weird part is that proving this also creates a contradiction.