We use computers in our everyday lives: doing work, playing games, reading blogs... but the computer's hardware would be useless without software: the programs that it runs. Usually, a program with an input will eventually halt and return an output. However, sometimes, the program will get stuck in a loop and never halt. Is there some kind of program that, given a program and an input, determine whether that program will halt? This is the Halting Problem, and it was eventually proven by Alan Turing to be impossible to create such a "Halting Program". Here is his proof:
Let's assume that a Halting Program does exist. It takes two inputs, a program and the input of that program, and outputs whether that program will halt as a yes-or-no answer. Then, let's feed the output of the Halting Program into another program called the Negator. If it receives the output "Yes, it will halt", it gets stuck in a loop and doesn't halt. If it receives the output, "No, it will not halt", it halts immediately. This entire machine is called "h+". What if we give h+ itself as an input? If the Halting Program thinks that h+ will not halt, the Negator will halt and the Halting Program will be wrong. If it thinks that h+ will halt, the Negator will not halt, and the Halting Program will be wrong again. So, by assuming that the Halting Program exists, we have run into a paradox, so the logical conclusion is that a Halting Program is impossible.
For more on the Halting Problem, please see the following websites:
https://www.youtube.com/watch?v=macM_MtS_w4
https://www.youtube.com/watch?v=92WHN-pAFCs
http://www.zutopedia.com/halting_problem.html#faq
Let's assume that a Halting Program does exist. It takes two inputs, a program and the input of that program, and outputs whether that program will halt as a yes-or-no answer. Then, let's feed the output of the Halting Program into another program called the Negator. If it receives the output "Yes, it will halt", it gets stuck in a loop and doesn't halt. If it receives the output, "No, it will not halt", it halts immediately. This entire machine is called "h+". What if we give h+ itself as an input? If the Halting Program thinks that h+ will not halt, the Negator will halt and the Halting Program will be wrong. If it thinks that h+ will halt, the Negator will not halt, and the Halting Program will be wrong again. So, by assuming that the Halting Program exists, we have run into a paradox, so the logical conclusion is that a Halting Program is impossible.
For more on the Halting Problem, please see the following websites:
https://www.youtube.com/watch?v=macM_MtS_w4
https://www.youtube.com/watch?v=92WHN-pAFCs
http://www.zutopedia.com/halting_problem.html#faq