Turing’s “Uncomputable” numbers
Below is a description of Turing’s argument, couched in modern terminology.
A description of an “uncomputable number”
First, Turing describes a method of assigning a natural number to any Turing machine - which in modern terms is equivalent to enumerating computer programs by assigning a different natural number to each computer program. To do this, all possible sequences of characters of the alphabet of given programming language are arranged in order according to their length, and for those of the same size, in an alphabetical order (note that this includes sequences that are not valid programs). This is called a lexicographical order.
Then, given such an enumeration, the argument that a real but uncomputable number r between 0 and 1 can be defined is as follows:
- Take one such enumeration of all possible sequences of characters of a computer programming language.
- The number r is defined to be in the binary base as a binary expansion.
- The initial part of the number r is “0·”, followed by the digits 0 or 1.
- If the nth program in the enumeration terminates the nth digit after the point is 0, otherwise if the nth program never terminates (or if the sequence is not a valid program) the nth digit of r is 1.
Turing claims that this number is “uncomputable” because it follows from his Halting Problem that there is no method of determining, for every program, whether it halts or does not halt. Therefore, while some of the digits may be calculated, there will be some digits for which there is no method of calculating whether the digit is 0 or 1, and so the number can never be computed. This means that there is no method (even in principle) that can continue to determine, on the basis of Turing’s definition, the digits of the binary expansion of the ‘number’ that is claimed to be given by the definition. (Footnote: Note that different computer languages will result in different sequences of 0s and 1s, but this does not affect the overall argument.)
We can analyze Turing’s “uncomputable” number in two ways:
- We can assert that for any given computer program, there is a truth value for the proposition “A theoretical computer with limitless memory will either stop or not stop when set to run the specified program”, even if we can never determine it. This is a Platonist stance.
- We do not assume that there is necessarily a truth value for the proposition “A theoretical computer with limitless memory will either stop or not stop when set to run the specified program”. This is a non-Platonist stance.
It is actually immaterial which stance one takes - Turing’s argument that he has defined a number that is actually uncomputable is logically invalid. To show that this is the case, we will consider both stances, taking the Platonist stance first.
Case 1: The Platonist stance
When we take the Platonist stance, we assume that there is a “true” value for every computer program as to whether it will stop or not stop, and so we assume that there is a definitive sequence of digits that corresponds to Turing’s definition, even if we can never determine that sequence. However, Turing’s definition does not actually prove that there cannot be a different definition of that precise sequence, and which need not make any mention of computers and whether they stop on certain computer programs.
If we take the Platonist stance, then Turing’s description only tells us that there is a number that cannot be determined from Turing’s description, but it does not prove that there cannot be any alternative definition of that number, and which does not refer to whether programs stop or do not stop. There could be an alternative definition that is a formula of some mathematical system, and which defines an algorithm that generates the sequence of the digits of the number.
The flaw in Turing’s claim is that he does not provide any proof that there cannot be an algorithm that generates the digits of his “uncomputable number”, but where its definition makes no reference to computer programs or to the halting of computer programs. Since that is the case, then it is possible that there could be an algorithm for Turing’s number, but we would not know that it was an algorithm for Turing’s number.
Since that is the case, we would still not have a method of solving the Halting problem, so there is no contradiction involved in the possibility of there being an alternative definition of Turing’s number that is in fact computable. Without any proof that such an alternative definition is impossible, there is no proof that Turing’s number is in fact uncomputable.
Case 2: The non-Platonist stance
In taking the non-Platonist stance, we do not assume that there must be a truth value for the question as to whether a particular computer program will stop or not stop. In this case, Turing’s definition does not in fact define a single specific sequence of digits but merely a constrained set of such sequences that satisfy certain properties. For example, it can be the case that a set of sequences have the first n digits in common, then the definition of such a set of sequences simply defines all sequence that begin with the same sequence of n digits. In binary terms, this would be that we can determine a certain number of 0s and 1s of a sequence, but only up to certain digit - if this sequence is, for example, 0.1010010110, then the definition simply defines a set of values between 0.1010010110 and 0.1010010111.
So if we do not assume that there must be a truth value for the question as to whether a particular computer program will stop or not stop, then Turing’s definition does not define a single number and Turing’s implicit claim that it defines a single specific number is incorrect.
It might be thought that there must be a ‘true’ or ‘false’ value, since the usual assumption is that every computer program either stops or continues to run forever. But computer programs don’t stop or continue to run forever. It is the computers that run the programs that stop or continue to run. One should not fall into the trap of assuming an extension from a real physical computer to a hypothetical abstract notion, and also assuming that all properties of the real computer extend to the abstract notion. Real physical computers will always stop at some point in time - they will eventually fail. And when they might fail is unpredictable.
It is no coincidence that the programs for which it might not be straightforward to determine if the computer they are set to run on will ‘stop’ or not ‘stop’ are those programs that involve a recursive loop, where there is at least one variable that increases in size at each iteration of the loop; in such a program the amount of memory required to run the loop and the increasing size of the variable increases every time the loop iterates. Since there are infinitely many programs, and infinitely many such loops, and infinitely many such variables, all of different maximum sizes, then no actual physical computer could run every such program, since it would require more than any fixed amount of memory. It follows that the notion that when a real physical computer that is set to run a program, it either ‘stops’ or ‘does not stop’, cannot apply to every such program, since we can only have a computer with a limited amount of memory.
It follows that when an actual physical computer is set to run a program, it is not a case that the computer either ‘stops’ or ‘does not stop’; it is essentially the case that it:
- runs the program correctly and stops, or
- it runs out of memory when it is set to run the program, or
- runs the program correctly, does not run out of memory, and does not stop (in this case it is stuck in a repetitive loop that does not require increasing amounts of memory).
Of course, it is obvious that Turing’s description does not depend on real physical computers; but Turing’s description assumes a hypothetical computer that has a limitless amount of memory and which is 100% reliable for all time. Such things do not actually exist. Of course, one can conceive of an abstraction where one assumes that there are abstract concepts that correspond precisely to the physical notions of ‘stop’ and ‘continue to run indefinitely’. This entails the assumption that one can apply either a ‘true’ or ‘false’ value to the purely abstract concepts that are assumed to correspond to the terms ‘stop’ and ‘continue to run indefinitely’. Of course, one can make such assumptions - provided that one doesn’t assume such assumptions are axiomatically true.
In summary, regardless of whether one applies a Platonist or non-Platonist interpretation, Turing’s claim that he has defined an uncomputable number is a claim that is unsupported by logical argument.
For an analysis of the similar claim by Gregory Chaitin that he has defined a number that must “exist” but which cannot be computed by any computer, see Chaitin’s Constant Error.