I was watching [this](https://youtu.be/eqvBaj8UYz4) video and even though I was trying very hard, there are some things that I still don’t understand. I get what’s Turing’s machine but I don’t understand what happens later. There’s some kind of paradox, that if you have machine that decides if programe will halt (solve the problem) at some point or just loop forever (not being able to solve problem) and then you give this infromation to another machine it’ll do opposite thing. So if the machine says “this program will halt” it’ll then loop forever and if says it’ll loop forever, then it’ll just halt.
I know it’s paradox so it isn’t supposed to make sense but well… I think I miss something here. Can someone explain it to me in the easiest way possible?
In: 5
Basically he shows that if it was possible to create a machine that could look at an arbitrary program and determine whether or not that program will eventually stop or otherwise go into a loop, then we could use that as the basis for building another type of machine (the “opposite” machine) which results in the paradox you describe. By inverting the output of the halting machine, then feeding its own code into itself, it can’t halt OR loop. Because if it halted, then by its own code it should loop forever. But if it looped forever, then by its own code it should halt. So it can’t do either.
But a program has to either halt or loop forever. There isn’t a third option. That means such a program can’t exist and since such a program is built on the notion of a halting machine, then a halting machine can’t exist.
Latest Answers