What is the Halting problem?
Q: What is the Halting problem?
A: The Halting problem is a problem in computer science that looks at a computer program and determines if the program will run forever or not.
Q: How do we know if a program solves the halting problem?
A: We say that a program "solves the halting problem" if it can look at any other program and tell if that other program will run forever or not.
Q: Is there a way to prove that no such program exists?
A: Yes, by showing that if there was such a program then something impossible would happen. This proof was found by Alan Turing in 1936.
Q: What does P do?
A: P is a function which evaluates another function F (called with argument I) and returns true if it runs forever and false otherwise.
Q: What does Q do?
A: Q looks at another program and then answers the question of whether or not running this same program on itself will result in an infinite loop. It does this by using P to make an evaluation of the given function F.
Q: What does R do?
A: R looks at another program and asks Q for its answer on that particular program. If Q answers "yes, if we run this program and make it look at a copy of itself it will run forever", then R stops; however, if Q answers "no, if we run this program and make it look at a copy of itself, it will not run forever", then R enters an infinite loop and runs forever.
Q: What happens when you make R look at itself?
A: Two things can happen - either R stops or runs forever - but both results are impossible according to what has been proven about programs like P not existing, so something must have gone wrong somewhere along the way leading up to making R look at itself.
