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
Feed
Twitter
Subscribe by email
What about a program that simply prints a random string of digits of random length (randomly prefixed with “0.” half the time? This will compute any non-irrational number if it’s allowed to run an infinite amount of time. (More precisely, as you allow it to run longer and longer, the chance of it printing any specific rational number approaches 1.)
It seems to me that the only “non-computable” numbers here are irrational numbers.
This is true. However, some programming languages have support for rational numbers (fractions), and can carry rational math forward such that no precision is lost. Common Lisp has this capability, so that if you multiple 1/7 by 2/5 you get 2 / 35 and no precision is lost until you need to cast that number as a floating point value.
@JoshJ: you right that all rational numbers are computable.
But, some irrational numbers are also computable, such as sqrt(2), pi or e.
> What about a program that simply prints a random string of digits of random length ..?
Random?
C# programs are uncountable. Just because program structure is defined doesn’t automatically make it countable. C# programs are capable of outputting literals like strings or numbers. In fact, with the proper set of print commands, one could generate any number desired.
For instance, follow the following sequence:
#1: static void Main() { Console.Write(“3.”); while(true) Console.Write(“1415″); }
#2: static void Main() { Console.Write(“3.”); while(true) Console.Write(“14159″); }
#3: static void Main() { Console.Write(“3.”); while(true) Console.Write(“141592″); }
#4: static void Main() { Console.Write(“3.”); while(true) Console.Write(“1415926″); }
etc. to its logical thing. Similarly, you could do that with all the rational numbers. Which is uncountable, ensuring that C# programs are uncountable.
To Brian.
I am not sure to follow your argument. But one thing is for sure: A C# program is a string of symbols, and you can associate a unique integer to such a string of symbols, hence there are a countable number of C# programs.
Are you sure your are not confused about the meaning of countable ?
Brian – look up countable & uncountable sets. You are wrong.
what about:
(assuming an arbitrary-length Real type)
void printAllPositiveReals(Number a, Number b)
{
Real mid = (a + b) / 2;
print mid;
printAllPositiveReals(a, mid);
printAllPositiveReals(mid, b);
printAllPositiveReals(b, b * 2);
}
printAllPositiveReals(0, 1);
This seems like it would print all positive real numbers, if you waited forever.
[btw: the comment text entry doesn’t seem to allow indents, which is why the program above doesn’t look very pretty]
My point is – although C# programs are countable and reals aren’t, a single program can compute more than a single number, so there doesn’t need to be a one-to-one mapping.
Anonymous #8
Your program does not print all positive reals. It does not even print all rationals, but only those whose denominator is a multiple of two.
Do C# programs have finite length?
If you could write a C# program of cardinality c (or above), obviously it could contain code to express every number in a set of cardinality c.
However, if C# program can only express finite or aleph-null numbers each, then a set of such programs of cardinality aleph-null would fall massively short.
I also agree with the last comment. Only if you assume a C# program is of finite length can you assert that the number of C# programs is countably infinite and thus it can only generate a countably infinite set of numbers. Given C# programs are infinite is length, then the valid (e.g. compilable) set of all subsets of this countably infinite number of C# programs will result in an uncountable number of programs that can generate and uncountable set of numbers. My real analysis is still a bit shaky, but this seems right. This follows a similar argument of generating the reals from the rationals.
The definition of a computable real number that I learned is as follows.
A real number a is computable if there is a computable function f from the natural numbers to the rational numbers such that given a precision parameter r, the following holds
|f(r) – a| <= 2^(-r)
Thus a computable real number is a number such that you can get a “close enough” approximate rational number given the function and the precision parameter r. It really has nothing to do with outputting exact typographical representations of the numbers i.e. printing out as many base-10 digits as possible. Also, a real number that has an infinite decimal expansion is not precluded from being a computable real number.
In response to whether programs are countable, yes they are. It does not matter what language you are using, they can all be reduced to (sometimes) complicated binary strings. The set of all such strings is countable, period. It does not matter what facility your program has for dealing with certain classes of numbers.
Brian is right: have Francois or flip got a refutation beyond “you’re wrong”?
Why assume that C# programs have finite length? No similar assumption was required by Turing…
If we assume that the C# program can have infinite length (a reasonable assumption seeing as we have unlimited resources), you could write an infinite number of programs with a distinct real number hard-coded into it. By directly applying Cantor’s argument that set of C# is now uncountable.
Yes, it doesn’t claim to be actually computing these real numbers, but it does disprove your underlying assumption of the number of C# programs being countable.
@Brian, Skippy, Rooster, James: We are assuming that any particular program is finite.
A non-computable number cannot be printed by any program which has a finite description. Of course, there is an infinite program that prints that number. But, if a computation does not have a finite description, can we call it a “program”?
Finite programs with access to infinite memory are the interesting combination. This is exactly how Turing machines work: they have a finite state space, but access to an infinite tape. (So, James’ comment that Turing machines don’t assume a finite description is not right.)
“Why assume that C# programs have finite length? No similar assumption was required by Turing…”
This isn’t true – Turing machines need to have a finite state set, finite alphabet. The “programming” in a program is, effectively, a really big state set – that is, the behavior of the TM is completely described by its states and transitions (finite). It’s true that TMs have an infinite /tape/, but this is a resource, not a part of the description of the “program” itself.
Agree a single C# program is countable. But surely it can produce multiple outputs. For the sake of argument let’s say it can print an infinity of different real numbers. So if we count the ouputs, not the C# program itself, then we have C# programs that can produce uncountable number of real numbers no?
I think people are misunderstanding the point of C# programs being countable, so to make it all easier, just take all positive integers (the set N) and convert it to binary. There you have all the source code in the world. Just a small subset of it being C# valid, and thus also countable.
First off, the number of C# programs must be countable. If we exclude any requirements of functionality and consider a ‘program’ to be a finite string of characters, one can easily put the set of ‘programs’ in 1:1 correspondence with the natural numbers. Explicitly: take the first program to be “a,” the second to be “b,” and so on until you run out of single characters, and continue with “aa,” then “ab,” etc. This construction will cover every possible finite string of characters. Now clearly the set of C# programs must be a subset of this set, and thus it must be countable.
What concerns me, however, is that I see no reason for the countability of C# programs to put a restriction on the countability of numbers they produce. It is exceedingly easy to produce uncountable sets from countable ones (e.g. the natural numbers are countable, but simply taking the power set of the naturals produces an uncountable set).
Consider that every real number (for simplicity we’ll restrict them to fall between zero and one) can be written as a countable string of digits. Furthermore, if you hand me any countable string of digits, I can give you a C# program that produces it. I follow you’re diagonalization argument (and, to be honest, I *really* like it), but I’m having trouble seeing how to reconcile it with this aforementioned fact.
@Ryan:
You’d have to figure out a way to generate 2^n things from n things, which is complicated at best. My hunch would be that it’s not actually possible to generate 2^aleph-null things from only aleph-null things using basic operations.
Also, I’m pretty sure that we’re all agreed that finite length programs imply a cardinality of at most aleph null.
Ryan says “It is exceedingly easy to produce uncountable sets from countable ones”. No, it is exceedingly difficult to do so. The power set is not at all well understood – we don’t even know the cardinalities of the smallest infinite power sets in the aleph sequence. It cannot be done at all in a constructive manner.
The power set operation on infinite sets cannot be implemented by any program. This follows immediately from two simple facts: Any program is a first-order formal system, and the Skolem-Löwenheim theorem says that any countable formal system has a countable model. So if you produced a program that you claimed implemented the power-set operation, it would have a countable model. An uncountable power set could not be in that model.
And even simpler: Church and Kleene counted all computable numbers a long time ago: The constructive ordinals is the counting set, and it has cardinality aleph-0, i.e it is countable.
Marvin Minsky gave several great examples of incomputable real numbers in chapter 9 of ‘Computation: Finite and infinite machines’.
Two quick comments:
1) I didn’t mean to imply that taking the power set of the naturals is exceedingly easy, and to do so in a constructive manner is certainly not. I was just pointing out that it is possible to derive uncountable sets from countable ones, and thus I see no empirical reason that the countability of C# programs should impose a countability restriction on their possible outputs.
2) I’d still like to see a concise rebuttal to the idea that, given any countable sequence of digits, there is a C# program which will produce it.
@Ryan: What do you mean by “countable sequence of digits”? Only sets can be countable or uncountable, not numbers.
You can easily write a program that prints any particular finite sequence of digits.
But, there certainly are infinite sequences of digits that no (finite) program will print. The construction in the article gives an example of one such sequence.
Does that clarify things?
Another way to look at this is in terms of compression — a program generating a number could be considered a compressed form of that number.
The question thus becomes, are there infinite sequences that are incompressible?
Is anyone else getting hard over this?
Placing the restriction “if a computation does not have a finite description, can we call it a ‘program’?” on this makes it trivial, doesn’t it? Of _course_ you can’t represent an uncountable set of outcomes with a countable set of inputs (the programs).
Without that restriction, which seems to me the only reasonable way to consider this, I think your argument fails.
>That is pretty surprising, given that both the number of real numbers and the number of C# programs are infinite.
This is “degrees of infinity” and a steaming pile of feces. Something is either infinite, or not. There are no degrees.
What’s that you say – there are infinite points on a segment, and also infinite points on the line containing that segment, but clearly the line has “more” points?
Hogwash. There is no such animal as “degrees of infinity.”
Bilgerat,
Please learn something about analytic math before making statements such as this (“There are no degrees [of infinity].”)
Degrees of infinity are a difficult thing to accept, but so was zero at one point. And negative numbers. And complex numbers. They’ve been accepted for over a century.
Yes, it is work getting past aleph-0 to aleph-1, and more work to get from aleph-1 to aleph-2, and even more work to start manipulating the orders of infinity to produce higher orders. But when you get there, you will have a certain mathematical awe. And integers will never look the same.
Back to the topic — uncomputable numbers. Anyone familiar with Gregory Chaitin and (big) Omega? Give it a whirl if you REALLY want your head messed with; it makes the orders-of-infinity issue childs-play. (Digits representing the probability that particular programs will halt; you can’t even talk about some of the digits having computable values…)
Steve
That’s not a number, that’s a string.
@Ryan:
>I’d still like to see a concise rebuttal to the idea that, given any countable sequence of digits, there is a C# program which will produce it.
Two responses: First, let’s say I give give you an infinite sequence of digits that come out of a true random number generator, such as decay times of radioactive particles (not a pseudorandom number generator). Do you think you can write a finite-length program that could produce this sequence?
Second, let’s say I give you the mathematical description of a sequence, and not the sequence itself. We’ve talked a little about Godel numberings of C# programs when we’ve talked about the cardinality of the set of C# programs. First, come up with a numbering system of C# programs so that every program is assigned a natural number, and every natural number is associated with some C# program. The sequence of digits I want your program to produce is this: Digit i is a 1 if C# program number i halts on input i, and is a 0 if C# program number i does not halt on input i.
If you could actually write a program to produce this sequence, you’d have solved the Halting Problem.
How about the following program?
while (true) {
bool p = Flip(); // some coin flipping function that produces 0/1 with probability 1/2 each
if (p)
print 1;
else
print 0;
}
Any real number can be an output of this program — of course I know that this is not what Igor had in mind.
But it is an interesting program anyway — it has uncountable outputs, in fact produces a uniform distribution over the reals in [0,1].
@VG
Pseudorandom number generators (e.g., Random(), rand(), etc.) that are implemented in software do not produce “real” random numbers. Pseudorandom number generators are periodic, that is to say, they repeat themselves after a while. Good implementations have periods of over 2^100, so the periodicity will never be noticed by real-world applications. But it implies that the algorithm you suggested will actually only produce a finite number of outputs, that finite number being the period of the Flip() pseudorandom number generator.
If you want to claim that Flip() produces “real” random numbers, those numbers have to come from outside the algorithm itself. The randomness may come from radioactive decay or atmospheric noise or some other source, and may be, to all statistical and mathematical tests, truly random. However, those random bits have to count as an input to your algorithm, as they are not part of the algorithm itself. Certainly, if the input to an algorithm is a noncomputable number, the output can be any computable function applied to that number.
For this discussion, it would probably be best to restrict to algorithms that don’t take any input. Rephrasing the question that way, it becomes “Are there real numbers that (finite length) computer programs cannot compute (without additional input)?” The answer is yes, in fact, there are.
Igor, interesting, but some of the statements are incorrect(ish). Yes, the set of C#, and any other programming language programs is countable, like the integers, rationals etc. But the set of outputs or traces of most practical languages is uncountable. As an excersise – you can write a program to create and traverse a tree with infinite number of of children nodes to a node. The data structure is definable – each node is a list of nodes. In fact this structure has the same size as the reals.
After reading a couple of paragraphs of the article I typed ctrl-F chaitin and found, to my surprise, that the autor didn’t mention him, and that tons of comments went by arguing about turing machines and random numbers without a reference to the Omega number.
Only “dr-steve” seems to know enough computer science to know what he is talking about.
Here: http://en.wikipedia.org/wiki/C.....s_constant
imho dikini has a valid point.
but also the author didn’t specify his problem correctly for his conclusion.
he asked if there are numbers that are non computable, then goes on about the countablitiy of C programs, but this really inst the issue (it would be if you want to assert you can compute ALL numbers of R with a program). but the countability of C programs has nothing to do with whether a specific number in R is computable. the uncountabilty of R implies you cant reach X from y without missing something, not whether Y is reachable at all.
as jungle and dr-steve mentioned Chaitlins constant. this might actually be incomputable. (likely is)
@dikini: You say that a set of programs is countable, but the set of their outputs is not. In this article, I assumed that each program takes no input, and produces exactly one output. In that case, there cannot be more program outputs than programs, and what you say is wrong.
We can relax the constraints in a couple of ways: we could allow a program to output multiple numbers, or take a finite amount of input. The set of program outputs becomes uncountable only if a program is allowed to accept an infinite amount of input.
@jungle: Chaitin’s constant is an interesting example of a non-computable number. But, it is not necessary to explain non-computable numbers, so I didn’t cover it in this article.
@pieterg: A number is computable iff it can be generated by a program. So, if programs are countable and each valid program computes one computable number, then all computable numbers are countable. This is a result of the Turing’s paper that I reference in the article.
[…] Numbers that cannot be computed | Igor Ostrovsky Blogging (tags: programming mathematics blog) […]
The example in the article seems wrong. It can be modified to show that natural numbers are uncountable:
Consider a natural number. We choose i-th digit (from right to left) to be different from the digit in the same position in the number printed by program i. So, each digit guarantees that the constructed number will differ from the number printed by a particular program.
just wow …
@Onan
That won’t be a natural number. It’ll have infinitely many digits.
Quick question,
does a program have to be writable in finite time to qualify as a program?
I’m guessing it has to be, otherwise the argument does not hold.
Integers are infinite and countable. No matter how long you pick a integer number, you can represent it in paper or a program. You can also count how many integers are betweens any two of them.
Real numbers are infinite but not countable. There are a infinite number of real numbers between two real numbers that cannot be counted. Even real numbers between 0 and 1 are not countable. Of course, some of the real numbers can be written, but most of then cannot be written in paper or in a program.
Programs are also infinite and countable. Given a finite alplhabet (a-z,0-9,etc), we can generate all posible strings in order and give each one a integer number. Some of this strings will be valid programs, other will not. But even counting the invalid ones, there will be as infinite programs as infinite integers, which are countable.
Hi everyone,
That’s a funny proof, but not real. Programs are simple uncountable. Imagine a program like:
static void Main()
{
Console.Write(a + “.” + b);
while (true) Console.Write(“0″);
}
Where a and b are the string representation of any natural number. So we can make a program for each (a, b). Now, by the diagonalization argument, it’s probed that this set of programs is not countable.
To Sergio: Note that “0001” and “1” are the same number, but can generate different programs.
Cheers
@elelias: You are right: programs have to be finite.
@Pablo: You can only write this program if the real number a.b has a finite decimal representation. Otherwise, you’d need an infinite program, and infinite programs are not allowed.
[…] de Microsoft que trabaja en computación en paralelo; escribió una interesante anotación titulada Numbers that cannot be computed donde describe un fenómeno curioso, los números que no son […]
@Pablo: as Igor has said, you can only write finite programs, but most of real numbers are infinite/uncountable, so you would never finish to write your program. This is different from integer numbers, because no matter how big is your number, you can always represent it with log2(number) bytes.
As an example, try to write the pi number here. You would NEVER finish to write it.
Sergio
I think it is uncountable infinite. If it is countable the computer can.
[…] de Microsoft que trabaja en computación en paralelo; escribió una interesante anotación titulada Numbers that cannot be computed donde describe un fenómeno curioso, los números que no son […]
1) Only that the number of programs is countable and the number of real floating point values isnt doesn’t actually prove that any of these values is NOT programmable. It only proves that it’s not possible to programm ALL of them.
2) The main problem with real floating point values is that not all are “Definable”. e.g.: Give me rule how the real number is defined and a program can be written to accomodate this rule.
Example: Calculation of Pi, e, Sqrt(2) etc.
3) The problem actually gets even worse: There is NO number for which you can “prove” that you cannot program it (assuming indefinite memory and processing power is provided).
-> To prove, you need a definition of the number to check the program against. But if such a definition exists, you then can create a program according to it.
1) Programs are countable, real numbers aren’t. So, there are fewer programs than there are real numbers. It follows that some real numbers don’t have programs that generate them.
2) “Definable” numbers are also countable, so some real numbers are not definable say in English. However, there are some numbers can be defined, but cannot be computed on a Turing machine. I gave an example of one such number (see my response to 3 below).
3) I gave an example of a number that cannot be computed in the article (see the paragraph on diagonalization).
By the way, check out http://en.wikipedia.org/wiki/Definable_numbers. The page explains this stuff better than I can. Here is a short quote from the article:
While every computable number is definable, the converse is not true: the numeric representations of the Halting problem, Chaitin’s constant, the truth set of first order arithmetic, and 0# are examples of numbers that are definable but not computable. Many other such numbers are known.
[…] Numbers that cannot be computed […]