Thursday, April 28, 2011

Can Irrational Numbers be Represented in a Computer?

I often see the following claim, or variants of it:

"In a computer (as we understand computers, at least), irrational numbers can't be fully accurately represented."

This one happens to be from Bradley Monton, Seeking God in Science: An Atheist Defends Intelligent Design, Broadview Press, 2009, p. 128, but Monton isn't alone.

This is a common misunderstanding that, I think, has two bases. First, for people without much mathematical training, a real number is inextricably linked with its base-10 (or perhaps base-2) representation. For them, the number π is 3.141592653 ..., as opposed to being defined by an integral or infinite series. Second, people without computational training often don't understand that some infinite objects -- including some base-10 or base-2 representations of irrational real numbers -- are routinely represented as finite objects in computers.

Let's take √2 as an example. Although it is irrational, symbolic algebra systems such as Maple and Mathematica routinely represent √2 "exactly" and allow manipulations with it. For example, if you type

> x := sqrt(2);
> x^2;

into Maple, it will happily return the "exact" answer 2. And, similarly, other arithmetic operations involving √2 will give the "exact" answers:

> expand((123+45*sqrt(2))^3);

3355317 + 2224665 √2;

Similarly, we can manipulate other famous irrational numbers such as e, π, etc, and often get "exact" results. The point is that many of the irrational numbers that people actually care about need not be stored in terms of their base-10 or base-2 representation.

But even if we insist that yes, they must be stored in this way, there can still be finite representations. For example, consider the base-10 number defined by having a "1" in the i'th digit if i is a perfect square (like 1,4,9,16, etc.), and 0 otherwise. Now it is easy to see that this number is irrational. But we can still store it in a finite way (for example, as a function that returns the i'th digit on input i), and do at least some simple manipulations on this representation. For numbers whose base-k representation is encoded by a finite automaton, for example, we can do addition, even if the carries come from "infinitely far" to the right. (This is not trivial.)

In fact, any algebraic number, and many others, can be stored as a finite program that on input i returns the i'th digit. In some cases we can even do this by a very simple recurrence. For example, Graham and Pollak, in a 1970 paper, gave a simple explicit recursion to compute the i'th bit of √2 .

The misguided claim I started with can be fixed. If instead we say, "The base-2 representation of most irrational real numbers is not compressible to a finite representation, so the entire base-2 representation of most irrational real numbers cannot be stored in a finite computer", we would be correct. Here "most" means "all but a set of measure zero". But this is not particularly interesting, since for actual computation we are rarely interested in "most" irrational numbers -- we are interested in the computable ones.

22 comments:

Joshua said...

Instead of "all but a set of measure zero" can't we use the stronger claim of "all but a countable set"?

Jeffrey Shallit said...

Of course!

John said...

"In a computer (as we understand computers, at least), irrational numbers can't be fully accurately represented."

If this means the base-10 (or base-2) representation (I'm pretty sure it probably does), then it can't be accurately represented on paper, in our brains or anywhere else. So what was his point?

KeithB said...

John, I'll bet he was claiming that a human can understand the abstract concept of sqrt(2), while a computer can only understand a binary expansion to some number of decimal places.

And Jeffery:
If the claim that the underlying *hardware* can't understand the concept of sqrt(2) he has a point. (Unless FPU's have a new capability I am not aware of.) However, since my neuron's don't have a concept of sqrt(2), I don't see his point.

Jeffrey Shallit said...

KeithB:

You'd lose that bet. The passage had nothing to do with human or machine understanding.

I don't even know what you are trying to say when you say "the underlying *hardware* can't understand the concept of sqrt(2)".

Jeffrey Shallit said...

John:

Actually, the base-2 representation of sqrt(2) can be accurately represented - which was one of my points. Storing each individual bit isn't the only way to represent an algebraic number.

Joshua said...

So why was Monton making these claims? My guess would have been along the lines of what Keith guessed. That seems to be a not uncommon line of argument among philosophers who want to argue that there's something intrinsically distinct about what humans do from what machines do. I have trouble coming up with other reasons an ID book would talk about this otherwise.

Jeffrey Shallit said...

The context was a discussion of whether we are living in a computer simulation; he argues that if we discover the fundamental constants have decimal representations that end at 16 digits, this would be evidence in favor of this, and if the fundamental constants are irrational, this would be evidence against this.

I think this is an extremely naive view of what is possible or not possible with computers.

Joshua said...

I'm inclined to somewhat agree with his point in that context. If it did turn out that there were a handful of basic constants in the universe and they were all rational numbers with a power of 2 in the denominator, this would be evidence that we exist in a very naive simulation. But this would be *weak* evidence.

Incidentally, does he propose a method for how we are supposed to even determine if a fundamental constant is irrational? That seems impossible given measurement constraints.

Jeffrey Shallit said...

Or, just as well, it could be evidence that the fundamental constants are themselves the result of some simple natural algorithmic process. I don't think either one is decidable.

Jeffrey Shallit said...

After all, the exponent in universal gravitation is 2, but nobody says that the fact that it is such a simple integer is evidence we are living in a simulation.

John said...

"Storing each individual bit isn't the only way to represent an algebraic number."

I know that. But my take on the context is that Monton believes that it is.

Sniffnoy said...

I think the bigger problem is that if you want to speak sensibly you have to talk about representing classes of numbers, not representing individual numbers!

John Stockwell said...

Monton is exhibiting apologist thinking. There are only two types of apologist argument. The first might be called an "argument from the credulity of the opponent", and the other is an "argument from ignorance".

When I was a kid, religious apologists would ask "have you ever seen an atom", implying that we take atoms on faith, and should take other things we can't see on faith, as well.

The second argument was "bumble bees cannot fly". This was an argument from the ignorance in that because the best models of flight at the time could
not account for the disparate wing loading/mass ratio of bumblebees.

Of course, neither of these notions work as apologetics now, because the nonlinear aspects of
insect flight were studied decades ago, and atoms are easily imaged via scanning-tunneling microscopes.

Takis Konstantopoulos said...

John Stockwell:

Religious people still ask such naive questions: Have you ever seen an ape-human? No? So evolution can't be true.

I have a question. Even though I did grow up in a religious country (Greece, where religion is not separated from the state), I've never heard such things. It therefore appears that utter stupidies of the above type are arguments used by specific groups of religious fundamentalists.

John Stockwell said...

To: Takis Konstantopoulos:

The religious apologetic is definitely
a Western phenomenon, though it could be picked up by Catholics, the idea seems to be practised largely in the Protestant world.

In the US religion is a kind of product that has its salesmen. Churches come in a huge variety.

As with any other type of consumerism, the salesman has to convince the potential customer that he/she has a need that will be met by the product, and that not having the product will make you somehow "deficient".

This is different from places where there is one dominant church, particularly if that church is supported by the government, or in some way intermingled with the government. In this way, the Church is more of an institution and less of a product.

Anonymous said...

Isn't there this ``interval-based'' representation that can represent any real numbers with arbitrary precision?

-A Nanny Mouse

Jeffrey Shallit said...

Isn't there this ``interval-based'' representation that can represent any real numbers with arbitrary precision?

Yes, but it is not the slightest bit relevant to what we are discussing.

Farhan Islam said...

I'd love to see you try and get the computer to plot the dirichlet function. You gave a pretty nice explanation, but even if you calculate pi upto a trillion digits, it is still rational. The computer cannot identify irrational numbers , like pi, because if it does, it technically should never stop computing it. For as soon as it does, pi becomes rational

Jeffrey Shallit said...

You're making two fundamental mistakes here:

#1: confusing the decimal representation of a number with the number itself. These are two different things.

#2: pi is an irrational number, and this fact has nothing to do with how many digits you calculate it to.

What does "the computer cannot identify irrational numbers" mean? Here is one model where this is clearly false. Given an automaton M that on input n in base k, returns the n'th digit of a number x written in base b, call x(M) the resulting real number. Then there is a decision procedure that, on input M, tells you whether x(M) is irrational.

Unknown said...

can you explain what you mean by "consider the base-10 number defined by having a "1" in the i'th digit if i is a perfect square (like 1,4,9,16, etc.), and 0 otherwise", and give an example?

Jeffrey Shallit said...

Well only one example is possible, which is the number specified by what I said:
0.100100001000000100....
It has a 1 in the first digit after the decimal point, in the 4th, in the 9th, etc. and 0's everywhere else.