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
> 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.
Yes. That’s the “opposite machine”. You give it any machine (or program; on an abstract level, there’s no difference between the two) as input, and it does the opposite of what that machine does.
The paradox comes in the next step: if the machine you give to the opposite machine as input is *the opposite machine itself.* Then, if the opposite machine halts, the opposite machine goes into a loop, and if the opposite machine goes into a loop, it halts. As a machine can’t halt *and* go into a loop at the same time, it follows that such a machine simply cannot exist. And as the opposite machine could easily be constructed from a decision machine, it follows that a decision machine cannot exist either.
Latest Answers