Copyright © James R Meyer 2012 - 2018 www.jamesrmeyer.com
In his paper On Computable Numbers… Alan Turing claims that he can prove that there are real numbers that “exist” but which cannot be computed by any computer, and proceeds to describe how there might be one such number. It seems to have been Turing who set the ball rolling on this notion, but it is Gregory Chaitin who has continued to keep this ball rolling, see the web-page Chaitin’s Constant Error. Both Turing and Chaitin make the same logical error in their claim that they have defined a number that is uncomputable.
Below is a description of Turing’s argument, couched in modern terminology.
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).
Then, given such an enumeration, the argument that a real but uncomputable number r between 0 and 1 can be defined is as follows:
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:
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.
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 the Omega definition, even if we can never determine that sequence. However, the Omega 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.
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:
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.
Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked. Difficulties in understanding the site content are usually best addressed by contacting me by e-mail. Note: you will be asked to provide an e-mail address - any address will do, it does not require verification. Your e-mail will only be used to notify you of replies to your comments - it will never be used for any other purpose and will not be displayed. If you cannot see any comments below, see Why isn’t the comment box loading?.
Please wait for comments to load …
There is now a new page on a contradiction in Lebesgue measure theory.
There is now a new page Halbach and Zhang’s Yablo without Gödel which analyzes the illogical assumptions used by Halbach and Zhang.
I found that making, adding or deleting footnotes in the traditional manner proved to be a major pain. So I developed a different system for footnotes which makes inserting or changing footnotes a doddle. You can check it out at Easy Footnotes for Web Pages (Accessibility friendly).
I have now added a new section to my paper on Russell O’Connor’s claim of a computer verified incompleteness proof. This shows that the flaw in the proof arises from a reliance on definitions that include unacceptable assumptions - assumptions that are not actually checked by the computer code. See also the new page Representability.
There is now a new page on Chaitin’s Constant (Chaitin’s Omega), which demonstrates that Chaitin has failed to prove that it is actually algorithmically irreducible.
For convenience, there are now two pages on this site with links to various material relating to Gödel and the Incompleteness Theorem
– a page with general links:
– and a page relating specifically to the Gödel mind-machine debate:
All pages on this website are printer friendly, and will print the main content in a convenient format. Note that the margins are set by your browser print settings.
Comments on this site are welcome, please see the comment section.
Please note that this web site, like any other is a collection of various statements. Not all of this web site is intended to be factual. Some of it is personal opinion or interpretation.
If you prefer to ask me directly about the material on this site, please send me an e-mail with your query, and I will attempt to reply promptly.
Feedback about site design would also be appreciated so that I can improve the site.
Copyright © James R Meyer 2012 - 2018