Turing's Legacy: The Limits Of Computation

Alan Turing (1912-1954)

Grading Scripts and the HELLO Assignment

Suppose we give you the following assignment: write a Java program to output the word "HELLO" on the screen and halt. Space and time are not an issue. The program is for an ideal computer. We will give you a PASS for any working HELLO program, and no partial credit.

Grading is done by a script. The grading script must be able to take any Java program and grade it.

How exactly might such a script work? What kind of program could a student who hated his/her TA hand in? How about this:

n:=0;
while(n is not a counter-example to the Riemann Hypothesis) 
    n++;

print "HELLO"

This nasty program gets a PASS if and only if the Riemann Hypothesis is false. In order to grade this program, would have to know whether the Riemann Hypothesis is true. But this is an open problem! Despite the simplicity of the HELLO assignment, there is no program to correctly grade it! This can be proved.

The theory of what can and can't be computed by an ideal computer is called Computability Theory or Recursion Theory.

Computable Functions

Fix any finite set of symbols, . Fix any precise programming language, i.e., Java. A program is any finite string of characters that is syntactically valid in the language. A function is computable if there is a program that when executed on an ideal computer, computes . That is, for all strings , .

There are only countably many Java programs. Hence, there are only countably many computable functions. How many functions are there?

There is a bijection between the set of functions and (the set of all subsets of ): for any subset of , the corresponding function is the such that

Then, the set of all such has the same size as the power set of . Since is countable, its power set is uncountably big. So, there are uncountably many functions. Thus, most functions from to are not computable. Can we describe an incomputable one? Can we describe an interesting, incomputable function?

Notation and Conventions

• Fix a single programming language.
• When we write program we are talking about the text of the source code for . So, is a string.
• means the output that arises from running program on input , assuming that eventually halts.
• means does not halt on .

The Halting Problem

It follows from our conventions that means the output obtained when we run on the text of its own source code.

Let be the set of all programs such that halts. is called the halting set. Is there a program HALT such that

The Halting Problem is the problem of deciding whether a program is in the set . The program HALT, if it exists, does exactly this; HALT solves the halting problem.

Theorem. There is no program to solve the halting problem.

Proof. (Due to Alan Turing, 1937). Suppose a program HALT, solving the halting problem, existed. Then, we can use HALT as a subroutine in another program called CONFUSE:

CONFUSE(P)
{
    if HALT(P) then loop forever;    // Do not halt.
    else return;                     // Halt.
}

// Text of subroutine HALT goes here.

Does CONFUSE(CONFUSE) halt? If the answer is yes, then HALT(CONFUSE) = yes. But then CONFUSE(CONFUSE) will loop forever. If the answer is no, then HALT(CONFUSE) = no. But then CONFUSE(CONFUSE) will return immediately (halt). Therefore, the program HALT cannot exist. If HALT were to exist, we could fool it by using it in CONFUSE.

Turing's argument is essentially a reincarnation of the diagonalization argument from the theory of infinite sets. Programs (computable functions) are countable, so we can put them in a (countably long) list. If we list the programs in the rows, the inputs (programs) in the columns, and write "yes" in cell if halts and "no" otherwise, the list might look like this:

		yes		no
	yes			yes
	no	no

Note that . By the definition of CONFUSE, halts if and only if . Therefore, CONFUSE behaves differently from program on the th input (the text of the program itself), so CONFUSE is not on the list.

A Real Number that is Describable but not Computable

Is there a real number that can be described, but not computed? Consider the real number whose binary expansion has a 1 in the th position if and only if . That is, the th digit is 1 if and only if . Suppose the program FRED computes this real number. Consider the following program:

MYSTERY(P)
{
    j := 0;
    do forever
    {
        if(P == P_j) then
        {
            use FRED to compute the jth bit of r
            return "yes" if the bit is 1, return "no" if the bit is 0
        }
        j++;
    }
}

MYSTERY solves the halting problem! Therefore, FRED cannot exist, and is not computable.

Computability Theory

We call a set decidable or recursive if there is a program such that:

We already know that is undecidable. The program can be thought of as computing a function . So, the statement " is decidable" is equivalent to the statement " is computable." is called the characteristic function for the set .

We call a set enumerable or recursively enumerable (r.e.) if there is a program such that prints an (infinite) list of strings, and each element of appears in the list after a finite amount of time. Also, all elements printed in the list are in .

Is Enumerable? The following program enumerates :

n := 0;
do forever
{
    loop through all strings of length <= n. let w be a string and
        simulate w(w). if w(w) halts in n steps, then output w
}

So is not decidable, but it is enumerable! Let . Is enumerable? If were enumerable, then the halting problem could be solved by running an enumerating program for and another for concurrently, and waiting until appears in either one enumeration or the other. Therefore, cannot be enumerable.

Oracles and Reductions

Now that we have established that the halting set is undecidable, we can use it as a jumping-off point for more "interesting" undecidability results.

An oracle for a set is a function that decides, for any input , whether or not is in , without regard to questions of decidability or computability. For example, if is the set of odd natural numbers, an oracle for would answer "no" when given 4, and "yes" when asked about 81.

Let be the set of programs that take no input and halt. Suppose you want an oracle for , but you only have an oracle for . What can you do? You can use the oracle for to build an oracle for . Here's how: for each program , take the source of and inline it into the program, giving it some variable name. Then, run the program so that it takes its input from the variable. Call the transformed program . if and only if .

The result is that if were decidable, would be decidable as well. But it isn't. Therefore, the set of programs that take no input and halt is also not decidable.

Let HELLO be the set of programs that print "HELLO" and halt. Let be with all print statements removed. Now, look at programs of the form . halts if and only if such a program prints "HELLO" (and halts). Therefore, if HELLO were decidable, it could be used to decide . But is undecidable, so HELLO is also undecidable. So, the grading script mentioned at the beginning cannot exist! Actual grading scripts use a time limit when testing programs. A program that takes too long to show the required behavior might not halt. Even if it does, there is something wrong with it if it takes too long.

Let EQUAL be all such that and have identical output behavior on all inputs. Halting with input, halting without input, HELLO, and EQUAL are all undecidable.

Diophantine Equations

Consider the equation

Do this polynomial have an integer root? I.e., does it have a zero at a point where all variables are integers? More generally, given a multi-variate polynomial over the integers, does it have an integer root? Consider the set

Famous theorem: is undecidable! (This is the solution to Hilbert's 10th problem).

Polynomials can encode programs. There is a computable function such that program halts if and only if has an integer root. Therefore, if were decidable, it could be used to solve the halting problem.

Problems that have no obvious relation to halting, or even to computation can encode the halting problem is non-obvious ways. Do these theorems about the limitations of computation tell us something about the limitations of human thought?

Philosophical Interlude: The Church-Turing Thesis

The Church-Turing thesis: any well-defined procedure that can be grasped and performed by the human mind and pencil/paper, can be performed on a conventional digital computer with no bound on memory.

The Church-Turing thesis is not a theorem. It is a statement of belief concerning the universe we live in. Your opinion will be influenced by your religious, scientific, and philosophical beliefs.

• Empirical intuition: no one has ever given a counter-example to the Church-Turing thesis, i.e., no one has given a concrete example of something humans compute in a consistent and well defined way, but that can't be programmed on a computer. The thesis is true.
• Mechanical intuition: The brain is a machine. The components of the machine obey fixed physical laws. In principle, an entire brain can be simulated step by step on a digital computer. Thus, any thoughts of such a brain can be computed by a simulating computer. The thesis is true.
• Spiritual intuition: The mind consists of part matter and part soul. Soul, by its very nature, defies reduction to physical law. Thus, the action and thoughts of the brain are not simulable or reducible to simple components and rules. The thesis is false.
• Quantum intuition: The brain is a machine, but not a classical one. It is inherently quantum mechanical in nature and does not reduce to simple particles in motion. Thus, there are inherent barriers to being simulated on a digital computer. The thesis is false. However, the thesis is true if we allow quantum computers.

There are many other viewpoints you might have concerning the Church-Turing thesis. But this ain't philosophy class!