jump to navigation

Turing’s library June 19, 2016

Posted by Ezra Resnick in Computer science, Logic.
add a comment

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[0] 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.


Theirs is a repressive, hateful ideology June 14, 2016

Posted by Ezra Resnick in Equality, Politics.
add a comment

After Omar Mateen killed 49 people in a gay nightclub in Florida, Speaker of the House of Representatives Paul Ryan tweeted “We pray for those brutally attacked in Orlando”, followed by:

It is horrifying to see so many innocent lives cut short by such cowardice. Tonight, and in the long days ahead, we will grieve with the families…

As we heal, we need to be clear-eyed about who did this. We are a nation at war with Islamist terrorists. Theirs is a repressive, hateful ideology that respects no borders…

I’m certainly not going to minimize the problem of Islamist terrorists; and yet, they don’t hold a monopoly on repressive, hateful ideology. Take Paul Ryan, for instance. He has voted against same-sex couples adopting children in Washington D.C., opposed the repeal of the “don’t ask, don’t tell” policy (which barred openly gay persons from military service), and supported a constitutional ban on same-sex marriage. In other words, he has actively contributed to the denigration and demonization of gays in our society, and has helped perpetuate the discrimination and injustice they face. And then, when gays are targeted for violence, he condemns someone else’s hateful ideology.

Perhaps, instead of praying, the Speaker could try doing something actually useful: he could speak up in support of equal rights for all, and against the dogmas that divide us — domestic as well as foreign. Being clear-eyed about one’s own failings does take courage; but Paul Ryan is no coward, is he?