This page is keyboard accessible:
• Use Tab, Shift + Tab keys to traverse the main menu. To enter a sub-menu use the Right Arrow key. To leave a sub-menu use the Left Arrow or the Escape key.
• The Enter or the Space key opens the active menu item.
• To skip the menu and move to the main content, press Tab after the page loads to reveal a skip button.
• To get back to the top of the page anytime, press the Home key.
• For more information, click here: Accessibility   Close this tip.

Note: Full functionality of this web page requires JavaScript to be enabled in your browser.
 

“Uncomputable” numbers

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.

 

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).

 

Then, given such an enumeration, the argument that a real but uncomputable number r between 0 and 1 can be defined is as follows:

  1. Take one such enumeration of all possible sequences of characters of a computer programming language.
  2. The number r is defined to be in the binary base as a binary expansion.
  3. The initial part of the number r is “”, followed by the digits 0 or 1.
  4. 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:

  1. 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.
  2. 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 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.

 

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:

  1. runs the program correctly and stops, or
  2. it runs out of memory when it is set to run the program, or
  3. 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.

 

Summary

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.

 

 

Footnotes:

 

 

 

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 …  

 

The Lighter Side

 

NEWS

Lebesgue Measure

There is now a new page on Lebesgue measure theory and how it is contradictory.

 

 

Illogical Assumptions

There is now a new page Halbach and Zhang’s Yablo without Gödel which demonstrates the illogical assumptions used by Halbach and Zhang.

 

 

Peter Smith’s ‘Proof’

It has come to my notice that, when asked about the demonstration of the flaw in his proof (see A Fundamental Flaw in an Incompleteness Proof by Peter Smith PDF), Smith refuses to engage in any logical discussion, and instead attempts to deflect attention away from any such discussion. If any other reader has tried to engage with Smith regarding my demonstration of the flaw, I would be interested to know what the outcome was.

 

 

Easy Footnotes

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).

 

 

O’Connor’s “computer checked” proof

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.

 

 

New page on Chaitin’s Constant

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.

 

Previous Blog Posts  

 

13 May 2015 Good Math, Bad Math?

 

30 Apr 2015 The Chinese Room

 

31 Mar 2015 Cranks and Crackpots

 

16th Mar 2015 Bishops Dancing with Pixies?

 

23rd Feb 2015 Artificial Intelligence

 

Links  

 

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:

Gödel Links

 

– and a page relating specifically to the Gödel mind-machine debate:

Gödel, Minds, and Machines

 

Printer Friendly

 

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.


Note: for some browsers JavaScript must be enabled for this to operate correctly.

 

Comments

 

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 - 2017  
www.jamesrmeyer.com