Turing’s library June 19, 2016Posted by Ezra Resnick in Computer science, Logic.
Tags: Halting problem
You are in an infinite library, containing the code of every possible computer program. In the library’s central space there is a computer that can be used for running the programs: you enter the code of the program you wish to run, along with the program’s input, then you push the Run button. A red light indicates that the program is running. Some output may be printed, and when the program’s execution is complete the light goes off. For some programs and inputs the run ends almost immediately, but for others the light stays on for a long time. If you get tired of waiting for the computer to halt, you can always press the Abort button to stop the current run.
Some programs in the library are short and simple, like this one:
Program M [input: two numbers, a and b]
Print the sum of a and b.
Unsurprisingly, running Program M with the numbers 2 and 3 as input prints “5”, denoted M[2, 3] = 5. Some programs are much more complex, of course. There is a program that translates English text to Japanese; a program that computes the shortest route between any two cities on a map; a program that, given the state of the board in a checkers game, finds the optimal next move.
Some programs take a long time to run, but you notice that some programs are guaranteed to never halt, at least for some inputs. For example:
Program N [input: a number, n]
As long as n equals 0, keep printing “0”.
For any nonzero input, Program N halts immediately; but N gets stuck in an infinite loop, printing zeros forever (or until you hit the Abort button).
Unfortunately, you find that for many programs you cannot easily tell just by examining their code whether or not they will run forever. If a program is still running after a week, or a year, should you give up and abort? Perhaps it only needs a minute more, or an hour, or a day — or, it might be stuck in an infinite loop that will never end. It occurs to you that it would be nice to know in advance, before running a program, whether it will eventually halt (for a given input), or whether it is destined to run forever. Surely, you think, there must be a program somewhere in the library that can answer that question! After all, a computer program is just text, so there’s no reason why the code of one program cannot serve as the input for another. The special program you are seeking, call it Program H, would take as its input the code of the program to be evaluated (p), along with that program’s proposed input (i); Program H would then print “True” (i.e., H[p, i] = True) in cases where p[i] would halt, or “False” (i.e., H[p, i] = False) in cases where p[i] would run forever. You spend a long time searching the library for Program H.
One day you happen upon someone who introduces himself as the librarian. Excited, you describe Program H, and ask where in the library it can be found. The librarian smiles. The library is infinite, he says, containing every possible computer program — but none of them is Program H. You ask how he can be certain, since by his own admission the library is infinite. Let me prove it to you, he says. If Program H existed in the library, there must also exist Program G, defined as follows:
Program G [input: the code of a computer program, x]
Use the same method as Program H to determine whether program x will halt when running with the code of program x as its input. If so (i.e., H[x, x] = True), then loop forever; otherwise (i.e., H[x, x] = False), halt.
Now, says the librarian, ask yourself: What will happen if we run Program G with its own code as input? Will G[G] run forever or halt? We ought to be able to compute the answer using Program H. Let’s first assume that H[G, G] = True, which means that G[G] will halt. But, based on the definition of Program G, G[G] would only halt if Program H reports that G[G] will not halt, i.e., H[G, G] = False — contradicting our assumption. Let’s assume, then, that H[G, G] = False, which means that G[G] will not halt. But, based on the definition of Program G, G[G] would only fail to halt if Program H reports that G[G] will halt, i.e., H[G, G] = True — also a contradiction!
We therefore have no choice but to conclude that Program H is like a square circle: it cannot logically exist. The library is infinite, containing every possible computer program — but none of them is Program H: some problems are impossible to solve.
Look on the bright side, says the librarian, sensing your disappointment. What’s that, you ask. The librarian smiles: At least you won’t waste any more time searching for something that isn’t there.