Computable real numbers

[cragar]

I was watching a lecture on computable real numbers, And in the lecture they talked about how this set of numbers is countable. And I could see this because the numbers that a computer generates would be listable, I could write them down on a list. For example pi is a computable real number. But it seems like I should be able to construct any real number with like an infinite series or something. But then again we have cantors diagonal argument. It just seems a little strange to me. If I do a calculation it seems like i could come up with any real number. Like I couldn't know which real numbers i couldn't compute. And like if I was trying to compute something, it wouldn't be like, well you can't do this calculation because your trying to compute an uncomputable real.

 

[Number Nine]

And like if I was trying to compute something, it wouldn't be like, well you can't do this calculation because your trying to compute an uncomputable real.

Your calculation wouldn't fail, it just wouldn't exist. If a number is not computable, then by definition there is no finite, terminating algorithm that can generate it to some arbitrary degree of precision. The number of turing machines implementing such finite, terminating algorithms are countable, and thus there must necessarily be an uncountable set of non-computable numbers, since the reals are uncountable.

 

[phinds]

For example pi is a computable real number.

I'm not a mathematician, so it's possible that "computable" means something to mathematicians that is not what I think. What I think is that "computable" means you can get a specific answer. In that sense, pi is not computable. In what sense is it to you that pi IS computable?

 

[Number Nine]

I'm not a mathematician, so it's possible that "computable" means something to mathematicians that is not what I think. What I think is that "computable" means you can get a specific answer. In that sense, pi is not computable. In what sense is it to you that pi IS computable?

For any n, pi can be computed to n decimal places using a finite, terminating algorithm, which is the definition of computable in this context.

 

[phinds]

For any n, pi can be computed to n decimal places using a finite, terminating algorithm, which is the definition of computable in this context.

Makes sense. Thanks. Just not what I would have expected.

 

[D H]

I'm not a mathematician, so it's possible that "computable" means something to mathematicians that is not what I think. What I think is that "computable" means you can get a specific answer. In that sense, pi is not computable. In what sense is it to you that pi IS computable?

You can express pi compactly in terms of an infinite series. Or an infinite product. Or a continued fraction.

I'll demonstrate with e rather than pi. You know this series:
$$e^x = \sum_{n=0}^{\infty} \frac {x^n}{n!}$$
So set x=1:
$$e=\sum_{n=0}^{\infty} \frac {1}{n!}$$

Nice and compact. It's easy to write this series as a finite sized algorithm, and that algorithm is easily adapted to computing e to any desired precision in finite time.

That is not the case for almost all real numbers. (Note well: "almost all" has a very specific meaning here.) There's no way to represent most ("almost all") real numbers compactly, and hence there's no way to write a finite length algorithm to describe them.

 

[phinds]

... hence there's no way to write a finite length algorithm to describe them.

My misunderstanding was not about the ability to represent a quantity compactly but rather with the concept that "computable" means "computable to a specified number of digits".

 

[D H]

A number that cannot be represented by a finite length algorithm is not computable.

 

[cragar]

A number that cannot be represented by a finite length algorithm is not computable.

What do you mean by finite length algorithm? Is an infinite series to construct pi considered a finite length algorithm. I am not trying to construct reals to infinite precision but rather wonder if we could construct them at all with some kind of series or something. Would it be possible to construct the reals with some uncountably infinite process using known reals that self-evolved to created an uncountable number of reals?

 

[Number Nine]

What do you mean by finite length algorithm? Is an infinite series to construct pi considered a finite length algorithm.

For any n, the first n digits of pi can be computed by a terminating algorithm in finite time. This is the definition of "computable".

 

[Deveno]

just as the rationals are dense in the reals, the computable numbers are also dense in the reals.

actually exhibiting a "non-computable real number" is a bit of a challenge (we would have no way of computing it, for example). we can start the calculation of such a number, but we can't finish it (we could, for example, use a random number generator to generate decimal digits, but we'd have to commit to letting the program run forever).

there are subtleties of infinity involved, here, the difference (in qualitative terms) between "almost" and "is" is quite vast. there are some who think the current definition of real numbers is not well-founded, because MOST real numbers cannot even be named.

and even a very "small" subset of the reals, like the cantor set, has this problem. some people find this troubling.

this is what zeno was getting at, with his paradoxes. one we commit to the continuum, we have the very large buried in the very small. this fine-patterned distribution of numbers we can describe amidst the sea of numbers we cannot, persists at all scales of resolution.

 

[D H]

this is what zeno was getting at, with his paradoxes. one we commit to the continuum, we have the very large buried in the very small. this fine-patterned distribution of numbers we can describe amidst the sea of numbers we cannot, persists at all scales of resolution.

This is not what Zeno was getting at with his paradoxes. The concept of computability did not exist in Zeno's time. The concept of the reals did not exist in Zeno's time. Zeno's paradoxes are much more easily explained in that even the concept of limits did not exist in Zeno's time.

Saying that Zeno was getting at something as complex as computability is historical revisionism.

 

[wisvuze]

I'm not a mathematician, so it's possible that "computable" means something to mathematicians that is not what I think. What I think is that "computable" means you can get a specific answer. In that sense, pi is not computable. In what sense is it to you that pi IS computable?

There are even representable numbers that are not computable, and there are numbers that are not even representable at all. That is, a number is representable if there is a formula in your language ( ZFC ) that specifies it. If this formula is recursive as well, then the number is computable. It is a well known deficiency of first order languages, that we cannot express everything that is "possible" in mathematics

Here is a representable/definable number that is not computable:

http://en.wikipedia.org/wiki/Chaitin's_constant

 

[Stephen Tashi]

I've always found it interesting that probability theory casually assumes that we can draw random samples from a continuous distribution, say, the uniform distribution on [0,1].

In practice, there is no way to do this. A physical method of implementing (like throwing darts or something) produces measurements that have only finite precision.

What about simulating the process with a computer? It is not true that numbers represented on a computer can have only a finite precision. The usual way of representing numbers on a computer has only finite precision, but one could use other ways. For example symbols representing irrational numbers such as $\pi$ or $\frac{ \sqrt{2}}{3}$ can be represented on a computer. Yet that does not solve the problem of creating a uniform random sampling algorithm on [0,1].

I wonder if the existence of non-computable numbers can be used to prove that there is no algorithm that can sample from a uniform distribution on [0,1]. We could allow the algorithm to have "genuinely" random input from some physical source that produced a uniform distribution on a set of integers {1,2,..n} since that doesn't involve assuming there is a physical way to sample with infinite precision. So the algorithm would not be entirely deterministic and would not provide a way to compute a specific number from a description such as "the 3rd sample drawn".