Did you know that there are numbers that cannot be computed by any computer program? It is weird, but true.
And by number, I mean just an ordinary real number. As a perhaps unnecessarily simple example, the result of the division 1/7 looks like this:
0.1428571428571428571428571428571414285714285714285714285714285714…
We can easily implement a program that prints this number. The decimal expansion of 1/7 is infinite, so the program will have to run in an infinite loop to print the “whole” number. Here is a C# implementation:
static void Main() { Console.Write("0."); while (true) Console.Write("142857"); }
It is a bit of a philosophical question whether this program is really “computing” 1/7 or whether it has the answer hard-coded. You can certainly write a program that will compute the answer more legitimately by long division. The part that really matters is that there is some program that prints the infinite decimal expansion of 1/7, which makes 1/7 a computable number.
Similarly, you can write programs that will print the infinite decimal expansion of any rational number, sqrt(2), any algebraic number, π, e, and just about any other number that you can describe. For example, to compute π, you could use one of the known approximation algorithms. You would compute π to greater and greater accuracy, and print more and more digits to the screen. As a side note, we are assuming that the computer that will execute your program has an unlimited amount of memory. While not very realistic, this abstraction is analogous to the famous Turing machine, and extremely useful to understand certain deep truths about computation.
Interestingly, there are numbers that are non-computable. A number is non-computable if there is no program that prints its infinite decimal expansion (adding trailing zeros if a finite expansion is possible). How do we know that there are such numbers? The key insight is that there are more real numbers than there are C# programs. That is pretty surprising, given that both the number of real numbers and the number of C# programs are infinite. Nevertheless, it is true.
C# programs are countable. That means that we can assign a different positive integer to each program. The shortest valid C# program will be 1, the next shortest will be 2, and so forth. If there are multiple valid programs of the same length, we will sort the programs lexicographically and assign integers in that order. By the way, there are many different ways in which to define a “valid program”. One approach is to say that to be valid, the program must compile, run without exceptions, and print an infinite sequence of digits, separated at exactly one place with a decimal point.
Unlike C# programs, real numbers are uncountable. There is no way to assign a different integer to each real number… there are just too many real numbers! This fact was proved by Georg Cantor in a couple different ways, the most famous of which is the diagonalization argument.
Not only do non-computable numbers exist, but in fact they are vastly more abundant than computable numbers. Many, many real numbers are simply infinite sequences of seemingly random digits, with no pattern or special property. But, even though there are so many uncountable numbers, their examples tend to be weird and a little strenuous to explain.
As one such example, consider a number whose part before the decimal point is 0. We choose i-th digit after the decimal point to be different from the digit in the same position in the number printed by program i (by “program i”, I mean the program associated with integer i, as described earlier in the article). So, each digit after the decimal point guarantees that the constructed number will differ from the number printed by a particular program. This demonstrates that the constructed number will be different from any number printed by a computer program! By the way, this construction is basically Cantor’s diagonalization argument, only recast in a different terminology.
Theoretical foundations of computer science, which underlie everything we do as programmers, are nothing short of amazing. If you would like to read more about computability and related concepts, check out Charles Petzold’s book, The Annotated Turing. The original Alan Turing’s paper that introduces computable numbers is available here, but Petzold’s book is a lot easier to read.
[Update] See the forum on the reddit page of this article for additional in-depth discussion of this topic.
More articles:
Data structure zoo: ordered set
Tags: Cool
[…] Numbers that cannot be computed […]
[…] Numbers that cannot be computed […]
Simply put, some numbers are random.
PI and E are not at all random, but just the opposite, they have a very specific derivation.
A very nice article, this one.
Most uncomputable numbers are hard to describe because if you could describe them, then you could turn that description into a program and they would not be uncomputable.
One exception is Chaitin’s constant Omega, the probability that a random program will halt. http://en.wikipedia.org/wiki/C.....s_constant
Hi,
Thanks for this post! But I still don’t understand how you would use the diagnolisation method to prove that some numbers are non-computable?
Please help!
Many Thanks!
re: “… you can write programs that will print the infinite decimal expansion of any rational number, sqrt(2), any algebraic number, π, e, and just about any other number that you can describe.
While 1/7, your opening example, is a “rational” number, these follow-on examples (sqrt(2), π, e) are _irrational_ numbers.
Perhaps in your text it would be better to to just say:
“… any rational number, any algebraic number, any transcendental number …”
Rational numbers expand to some repeating sequence of digits: the 142857 of your 1/7 example, or the 0 of integers.
Irrational numbers have a non-repeating decimal expansion.
They are “computable” to any level of precision you wish.
The set of all irrational numbers is “uncountable”, as shown by the diagonal argument.
But be careful, “not computable != not countable”.
The Real Number set is uncountable, but every number in that set is computable.
The diagonal argument only shows that the set is uncountable.
SUMMARY (of diagonal argument):
* If they are countable, I can pick an order and list them all.
* Yet with the diagonal argument, I can make one that is not already in the list.
* Thus, I couldn’t have counted them and listed them _all_ in order.
So, if for “numbers that cannot be computed” you mean the _cardinality_ of the Real numbers, then OK. Infinity (aleph-1) can’t be computed. But then, the _cardinality_ of Integers is also an Infinity (aleph-0).
But if you only need a given precision (number of digits in the expansion), then any _number_ can be computed to that level.
Only the various values of Infinity “can not be computed”, and they aren’t really _numbers_. That is, they are not members of the Natural, Integer, Rational, Real or Complex number sets.
http://en.wikipedia.org/wiki/Aleph_number
-Jesse
In fact, there are real numbers that are not computable. One example is Chaitin’s constant. The Wikipedia page states that Chaitin’s constant is a real number, and also that it is not computable. Not only that, “nearly all” real numbers are not computable.
Of course – that is trivially true. There definitely is a program that prints Chaitin’s constant to 1,000,000 decimal places. A simple print statement will do.
Computability means something different.
A number is computable if there is a finite program that prints the number to arbitrary accuracy, given enough time.
Doesn’t this argument — that some numbers are uncomputable, since there are more real numbers than C# programs — only work for the Turing-class “programs”?
In fact, one program can generate lots of different numbers when run different times: just print the result of the random number generator, for example.
I still agree that there are more real numbers than programs in any language, but I don’t think this argument is necessarily a valid one.
tim: The argument is subtle, but definitely valid.
Printing lots of random numbers is not a counter-example. A program that prints many random numbers will never print PI. It may print PI up to a certain number of digits, and then it will have to switch to another number.
The only way to “print PI” is to have a program that never terminates, forever adding digits to the number.
This kind of a program can be written for the number PI (although it would require unlimited memory). But, such program *cannot* be written for the vast majority of real numbers, unlimited memory or not.
i´m not a physist, neither a mathmatician but I think that with a 5 dimentional plane a non coputable number could be explane because it could analize how it can´t be computaded in difents realitis.
and with no relativistic time, time wil be anlized by an absolute entanglement pick at random an the change of entanglements will be time but a nomalization from it´s first quatum state back to the start thats why an non coputable nomber can have an answer
or not, maeby i´m very ignorant
Non-computable numbers make perfect sense to me. Before complex numbers became ordinary in algebra they were considered anomalies or just not to exist. The same was also true before the irrationals became common in algebra. The Greeks called those numbers “incommensurable” and considered them to be an abomination. We know better now of course.
That there exist numbers that go against the grain of our current number system should not be too large of a surprise to anyone. The flaw is to assume that our number system is complete. In fact, other than the theorems proven by Kurt Godel and George Cantor, non-computable numbers is further validation of this simple fact. Whether or not this validation comes through computers or on paper through rigorous algebraic manipulation, is merely a matter of human abstract contrivance.
Another way the existence of non-computable numbers can be demonstrated is with complex valued functions. If it can be shown there exists at least one complex valued function that cannot have a solution that is real, irrational, transcendental, or complex, then the solution of the complex valued function is said either to “not exist” or is transcendent to any kind of number in our current system of algebra. There is more evidence in favor of the latter of these two (i.e. incompleteness, trans-infinite sets, diagonalization, …) than in the former of these two. Just because one cannot find a meaningful solution to a mathematical equation within the confines of the current math system does not mean “a solution” does not exist; it simply means a way to describe the solution does not currently exist.
We may use the same argument with our current knowledge of physics. Physics continues to demonstrate operative existential physical reality not currently discernible to us, whether directly, or through any clever instrumentation of our own making.
It would be hasty to assume all mathematics is known and all physical law is known just because it does not fit within the paradigm we are used to; that would just be unscientific.
We would do well to remember that everything we know is only a sliver of a greater and transcendent, abstract and physical, reality.
I thoroughly enjoyed your comments, Mr. Ostrovsky.
It seems to me that the meaningfulness or otherwise of the concept of non-computable numbers depends on ones attitude to the concept of infinity. If like me you consider that infinity is not a thing or a place or a number but a process then non computable numbers seem to be meaningless. The infinity process in question is the indefinite repetition of some recursive procedure – what would be refered to in common language as ” and so on and so on” or typographically by ………….
A proof of this statement from this point of view might run like this.
A program can be written that will print ( or store on disc) every possible decimal number of,say, 6 digits length. There are only 10^6 of them. The same program could run on ( for 10 times longer) and generate all possible numbers of seven digits and so on to 100 digits and so on to infinity…….. There are no non-computable numbers of length 100 digits or 1000 digits or any other number you care to specify.
Can anyone explain to me why this is not a proof of the meaninglessness of the concept of non-computable numbers without invoking the equally meaningless idea of actually reaching infinity?
David,
If you have a computable number, there is a fixed-size algorithm that can generate the number to an arbitrary precision. So, I can give you the algorithm, and no matter how many digits of precision you want, you can (in theory) use the algorithm to generate the digits.
If you have a non-computable number, there is NO fixed-size algorithm that can generate the number to an arbitrary precision. You can have an algorithm that generates the number to 1,000,000 digits. But if you want 1,000,001 digits of precision, you can’t use the algorithm.
So, computable numbers are not a purely theoretical/imaginary concept.
Igor,
Thanks for your response. However the process I sketched is surely realisable by an algorithm of finite size.
An array of 10^n rows x n columns will hold all possible decimal numbers of n digits in length. A procedure expressable in code of a quite modest size can then make a new array of size 10^(n+1) x (n+1) by, for example
1 Copy each row ten times
2 Insert the digit 0 – 9 in sequence onto the end of each row of a block of ten. This creates the new array containing rows listing all numbers of lenght n+1 digits
This procedure can, in principle, be repeated indefintely to any arbitrarly large value of n. To infinitely in fact.
Why is this not a proof of the non existence of any non computable number?
Examples that I have seen of “non computable numbers” make reference to programmes that could not be given since they are of infinite size. I could accept that this could be described as a non computable programme but it still seems meaningless to me to say that it corresponds to some non computable number.
David,
I misunderstood your original point somewhat. I see now that your program is generating all numbers, not just a particular one.
Your program does not disprove non-computable numbers because it does not follow the rules: the program should generate a single number – the number that is being “computed” – not all possible numbers.
For example, it wouldn’t be meaningful to say that your program computes PI. Sure, PI is going to be somewhere in the output, but to identify it, I first need to compute PI myself. So, your program is not helpful at all in computing PI.
In the discussion of computable numbers, a program must be generating a single number – the number that is being “computed”.
I am not sure what to make of your comments here. You seem to be introducing some extra rule that is not in Turing’s original definition. Turing gives only some very brief statements in way of definition which amount to the statement that a computable number is one whose decimal form can be written down by a Turing machine ( or algorithm ) of finite size. This my programme seems to do this for all possible numbers. It is true that as the programme progresses it makes increasingly huge demands on computing resources but is this relevant to the issue of principle involved here?
I should make it clear that I do not have any objection to what I see as the real content of Turing’s claims but only to the manner in which they are expressed. Let me briefly show why
Consider Turing’s procedure giving an example of a “non computable “number. I say procedure here rather than machine, algorithm or programme because Turing does not give any algorithm but only a procedure from which an algorithm could be constructed. We are invited to consider an infinite class of Turing machines and then construct algorithms to determine the halting property of each (or the circular property in Turing’s original terminology). The digits of a real number are then to be found in some way from the results of the halting tests or from the output of the machines that satisfy the halting test. Now it may be that the first Turing machines on our list are easily dealt with and a number of digits of the “non computable number” are obtained. Turing’s halting theorem however tells us that this easy success cannot continue since no single algorithm of finite size can decide the halting property of all machines in an infinite class. However Turing’s theorem does not show that any particular machine is absolutely un-decidable*. It remains possible to construct (in principle at least) some new testing algorithm that will do the job in any particular case. In this way unlimited progress can continue. There is no known limit to the number of digits of the “non computable” number that can be determined if one is prepared to deal with an algorithm of ever increasing size and complexity.
It must be admitted that such a task is of insuperable difficulty but my point is that it is misleading and confusing (to me at least) to attribute the responsibility for this difficulty to the intrinsic awkwardness of some particular real number. The difficulty lies in the horrendous nature of the algorithm. Thus I am led to consider that the concepts of computable numbers and non computable numbers are not to be taken too literally ( as I rather naively have been doing) but are only convenient metaphors for the more accurately descriptive terms computable procedures and non computable procedures or, better still, finitely programmable procedures and non finitely programmable procedures.
Footnote
*If this statement were untrue then the number in question would not be non computable but merely undefined.
Whats all the fuss about? You cant compute em, because they are as infinite as time! Done!
As long as time goes on we can compute them to as far as time will allow us…
Wait aren’t we then computing them to their limit? Well their limit/end is defined by processing speed relative to advancement of time… Sow we are except, its not a static limit! But a Dynamic one!
Well this could be a definition of non computability. There is clearly some semse to it However on this definition irrational numbers like the square root of 2 would not be computable ( since this would require an infinite number of digits). In Turings definition however they are computuble ( as I understand it because they can be computed to any accuracy by a programme of finite size). Here it is the finiteness or infiniteness of the programme that calculates the number that is important not the length of the number
Sorry, I disagree. C++ programs may be countable, but if the program uses a seed to generate some number (like generators for pseudorandom numbers do) then the number of possible seeds equals the number of real numbers.
In my earlier post (December 4th ) I suggested that the notion of computable and non computable numbers might be de mystified somewhat if we referred directly to their true nature which I called finite or non finitely programmable procedures. In the latter case further de mystification might be had by asking what kind of task or question requires an infinitely long programme to deal with it.
The answer is that the task or question that gives rise to the notion of non computable numbers is itself infinitely long. More accurately it is an infinite number of separate questions each one provided by a Turing machine. The code or description numbers describing these Turing machines is infinitely long even though it can be generated by a programme of finite size. Once this is recognised then it might not be too surprising that an infinitely long question only has an infinitely long answer!
Wow, such a great article! It took me a long time to read, and my brain nearly bled, but it was definately worth it!
Actually, only some C# program will generate a number. Since there are countable many C# programs, only countably many of them can generate a number. Since countable many of them generate a number, these exists a sequence of all computable numbers so by Cantor’s diagonal argument, there exists an uncomputable number. This does not tell you how to generate an uncomputable number in your head because we haven’t found a way to know which programs generate a number. When you think of a way to generate all numbers that can be generated in a system, you can use Cantor’s diagonal argument to think of a way to generate a number different from any of those numbers. Since only some of the algorithms that generate a number generate a number that can be generated in that system, that does not prove that there’s no algorithm that generates the number that can’t be generated in that system. A number is not said to be computable unless there exists a program that for each digit will only print that digit once without taking back any digits it has already printed, even if there is a program that for each digit will only change that digit finitely many times then eventually never changes it again.
In my earlier contributions to this discussion group I was hung up on the idea that while uncomputable procedures were meaningful the associated idea of an uncomputable numbers is not. I now want to correct matters by stating that in this I was wrong. One difficulty I had is that I had thought, incorrectly, that it would not be possible to give a specification of a number that didn’t then allow a finite- sized algorithm to be constructed that would compute that number. I now realise that specifications of a real number can be given such that the number could not be constructed to an indefinitely high precision by any algorithm of finite size. The simplest example of such a specification that I can think of is a variation of one I saw in the math.stackexchange.com discussion group. If I give here some detail on this it might help others who struggle as I did to come to terms with this idea.
The calculation of a real number is equivalent to the calculation of a string of digits. For simplicity I consider here the calculation of f, an endless string of the binary digits, 0 and 1 (any finite string would be computable since an algorithm of finite size could calculate it). Given an infinite set of Turing machines (with some fixed input if necessary) uniquely identified by an integer number, n, then fn, the nth digit of f, can be defined as
fn=1 if the nth Turing machine halts or fn = 0 if it doesn’t
If one were to embark upon a calculation of f one might initially be lucky in constructing an algorithm that determines the first digit and also the next few digits. However Turing’s halting theorem tells us that this success could not continue. No algorithm of finite size could determine the halting property of all the Turing machines. At some point a Turing machine would be encountered whose halting property could be determined only by the development of a new algorithm or, equivalently, the extension of a previous one. This would continue indefinitely and so the determining algorithm would grow indefinitely. At no point could one dispense with the attention of an intelligent and creative mind able to produce new or extended algorithms as one can in the case of computable numbers. For a computable string, like the numbers pi or e, intelligent input is needed only initially to create a single finite algorithm. After that an indefinite number of digits of the computable number can be determined by a machine that need have no intelligent understanding of what it is doing and has no need of any further instructions. That after all is why it is called computable.
In principle therefore the uncomputable string, f, can be calculated to an indefinite length, provided that the endless demand for new or extended algorithms can be met. Before anyone attempts to actually determine the digits of any string like that described here it is well to recognise the mathematical horrors that could be encountered in such an enterprise. Determining the halting property of a Turing machine could in effect require the solution of very difficult mathematical problems. For example, one Turing machine might be searching the natural numbers to look for an even number that cannot be expressed as a sum of two primes. An algorithm that determines the halting property of this machine would in effect determine the truth or falsity of the Goldbach conjecture, something that almost three centuries of mathematical endeavour has failed to do. Nevertheless, after a century or more of further effort this might be done – and then you could move on to determine the next digit !!