2 ms·
It 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
by chongli 8y ago
It 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]