EncycloZine

An Outline of Turing's Computability Proof

Alan Turing showed that there are real numbers that can't be computed. A real number such as 3.1415926..., is a length measured with arbitrary precision, with an infinite number of digits. And a computable real number is one for which there is a computer program or algorithm for calculating the digits one by one. For example, there are programs for pi, and there are algorithms for solutions of algebraic equations with integer coefficients. Turing proved this with the following steps:

1. Specify a mathematical computer.
2. List all such computers and their results.
3. Show that the results are incomplete - not all real numbers are listed.

The Turing Machine

The first step involved the famous Turing machine.

This is a device with a read/write head running over an infinite tape. The tape may be blank or have some symbols on it, in contiguous cells. So it's a sequence of zero or more symbols. The device has a finite number of states, and corresponding to each state and some (or all) of the symbols there are instructions which specify what to do, in a given state, when the head is reading some particular symbol. The instructions might be to move the tape left or right, or to write a new symbol, or change to a new state, or halt. Thus complex logical operations could be built up from a very small set.

So a Turing machine is specified by listing all the instructions, and what's on the tape. You can design Turing machines to do all sorts of mathematical computations, such as counting, or adding or multiplying numbers. And there is one special machine which can take a TM specification and some data, and can pretend to be that TM acting on that data. This is the Universal Turing Machine.

Later on, Turing got the idea to let those instructions be stored on the tape, too, to equate code with data, a idea that is fundamental to modern computers. It had little similarity to the classic 'von Neumann computer' of 1945, and was not well understood. However the paper anticipated many computer-related concepts, like input, output, memory, coded programs, algorithms, compilers/interpreters, and the finite-state machine.

Turing showed that the machine in principle was able to do all mathematical operations and that there was no general way to determine if a computation would ever stop. From this he concluded that it is not possible to determine if a theorem is provable or not without actually finding the proof.

I won't go into the details, because they can get tedious, and all that's needed in this age of digital computers is to appeal to your intuitions about computer programs. There were no digital computers in Turing's time, but in fact his ideas laid the foundations for modern computers - which cannot, in principle, do anything more than his UTM.

Enumerate all Programs

Imagine writing a list of all possible computer programs. You could list them in 'numerical order' - if you consider computer programs to be in binary, then list them as if they were the numbers those bits, taken all together, represent. Or, list the programs in alphabetical order - consider each program's source code in ASCII, and arrange them the way that your sorting program would.

Next to each computer program write out the real number that it computes if it computes a real (it may not). But if it prints out an infinite number of digits, write them out.

p₁ 3.1415926...
p₂ ...
p₃ ...
p₄ ...
p₅
p₆ ...
...

Maybe some of these programs don't print out an infinite number of digits, because they're programs that halt or that have an error in them and loop forever. Then there'll just be a blank line in the list. It's not really important - we'll just remove the 'duds'.

Following Cantor, let's go down the diagonal and look at the first digit after the decimal point of the the first number, the second digit after the decimal point of the second, the third digit of the third number, the fourth digit of the fourth, the fifth digit of the fifth. And it doesn't matter if the fifth program doesn't put out a fifth digit, it really doesn't matter.

Change every digit on the diagonal, e.g. by adding 1 to it, and if you get 10, call it 0.. Put these changed digits together into a new number with a decimal point in front, a new real number. That's Cantor's diagonal procedure.

p₁ -. d₁₁ d₁₂ d₁₃ d₁₄ d₁₅ d₁₆ ...
p₂ -. d₂₁ d₂₂ d₂₃ d₂₄ d₂₅ d₂₆ ...
p₃ -. d₃₁ d₃₂ d₃₃ d₃₄ d₃₅ d₃₆ ...
p₄ -. d₄₁ d₄₂ d₄₃ d₄₄ d₄₅ d₄₆ ...
p₅
p₆ -. d₆₁ d₆₂ d₆₃ d₆₄ d₆₅ d₆₆ ...
...
. ¬=d₁₁ ¬=d₂₂ ¬=d₃₃ ¬=d₄₄ ¬=d₅₅ ¬=d₆₆ ...

This new number cannot be in the list because of the way it was constructed. Therefore it's an uncomputable real number. We have described a number which is not computable - this seems to be a paradox since we appear to have described in finite terms, a number which cannot be described in finite terms.

However, Turing understood the source of the apparent paradox. It is impossible to decide (using another Turing machine) whether a Turing machine with a given table of instructions will output an infinite sequence of numbers.

To compute the Nth digit of this number, you get the Nth computer program and then you start it running until it puts out an Nth digit, and at that point you change it. The problem is, what happens if the Nth computer program never puts out an Nth digit? This is the halting problem ---you cannot decide whether the Nth computer program will ever put out an Nth digit! If you could solve the halting problem, then you could decide if the Nth computer program ever puts out an Nth digit.

If you could do that then you could actually carry out Cantor's diagonal procedure and compute a real number which has to differ from any computable real. But this would create a contradiction, since this would then be a computable procedure...

You can also informally appreciate the halting problem by considering the consequences of having a subroutine, e.g. Halts(P,d) which returns True if program P halts on data d, and False if not. What will this program H do:

	while	(Halts(H,H))	;

Program H halts if and only if Halts() says it doesn't, and loops forever if Halts() says it stops. So if you had an algorithm that could tell you if any program would eventually stop, you could easily build this new program and run it on itself...