4 ms·
> It's super easy to prove if you assume the Halting Problem is undecidable. Well, sure, because proving the Halting Problem is undecidable is about as hard as
by pdonis 8y ago
> It's super easy to prove if you assume the Halting Problem is undecidable.
Well, sure, because proving the Halting Problem is undecidable is about as hard as proving Godel's Theorem without having the undecidability of the Halting Problem to start from.
- chongli 8y agoIt isn't, actually. The proof of the undecidability of the halting problem is rather straightforward. You just assume you have a program that determines whether or not its input halts or loops. Then you write a program that uses your assumption as a helper and does the opposite: If the input halts, then loop If the input loops, then halt You then pass the program itself as input to itself and you get a contradiction.
- QuinnWilton 8y agoHere's my favourite version of this proof, in the style of a poem by Dr. Seuss: http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html
- deleted 8y ago[deleted]
- jcranmer 8y agoThe proof of the Halting Problem's undecidability is a lot less technically challenging. Here it is, off the top of my head: Assume you have a program HALT(n) that will return 1 if the Turing machine described by string n halts when fed itself as input and returns 0 otherwise. Construct the program BOOM(n) that runs forever if HALT(n) returns 1 and returns 0 if HALT(n) returns 1. Now consider HALT(BOOM). If HALT(BOOM) is 1, then BOOM(BOOM) halts by definition of HALT, but BOOM runs forever in that case. If it returned 0, then it runs forever, but BOOM(BOOM) in fact halted. Something must give, and the only thing that has room to give is that HALT itself can be constructed (since the encoding of Turing machines to numbers is well-defined, and the construction of BOOM is well-defined and possible iff HALT is well-defined and possible).