- #1

lavinia

Science Advisor

Gold Member

- 3,237

- 624

First - the decimal expansion is ultimately random - unpredictable

Second - The decimal expansion follows an algorithm

e.g. .01001000100001 .....

- Thread starter lavinia
- Start date

- #1

lavinia

Science Advisor

Gold Member

- 3,237

- 624

First - the decimal expansion is ultimately random - unpredictable

Second - The decimal expansion follows an algorithm

e.g. .01001000100001 .....

- #2

- 218

- 1

I am not too sure about what you mean.

What you are talking about are not rational numbers. rational numbers always have a repeating pattern.

if the decimal expansion is finite, you could say that the repeating pattern is just zeroes all along :)

otherwise it will be any pattern, but repeating always.

Now for unpredictable random digits, well, if you are thinking about some transcendental number like pi or e or whatever, there is no pattern, but that doesn't mean it is random, there are algorithms, or there can be algorithms to find the nth digit of any of those, in fact, any real number is eventually the limit of some rational sequence, so here is an algorithm, except it might be a bit more complicated than your example

On the other hand, maybe you are thinking about "uncomputabble numbers" like chaitin's Omegas and super Omegas, in which case this link might interest you

cheers...

- #3

- 795

- 7

Yes, what you are interested in is the

First - the decimal expansion is ultimately random - unpredictable

Second - The decimal expansion follows an algorithm

e.g. .01001000100001 .....

http://en.wikipedia.org/wiki/Computable_number

By the way, many numbers that "seem" random like pi actually follow algorithms. But some numbers are truly random -- they can't be described by algorithms. That's because there are only countably many algorithms (finite-length strings over a countable alphabet) but uncountably many real numbers.

- #4

Deveno

Science Advisor

- 906

- 6

pi is certainly computable, but there's no discernable pattern in the digits themselves (that is, pi itself is suitable for use as a (pseudo-) random number generator).

does there exist an algorithm for computing the n-th digit of pi, BESIDES computing pi to n digits and looking it up?

i think determining "which" irrational numbers have "predictable" digit patterns is a very deep, and unsolved (hard) question, related to the difficulty of determining if a given real number is even irrational (or even worse, transcendental).

for example: suppose i take...√2, for example, and i construct a real number between 0 and 1 in the following way:

the first decimal digit of √2 is 4, so i take the 4-th digit of the decimal expansion of pi, which is 5:

0.5......

the second decimal digit of √2 is 1, so i take the "next" digit of pi's decimal expansion:

0.59......

the third decimal digit of √2 is 4, so i take the 9-th digit of the decimal expansion of pi, which is 3:

0.593.....

can you tell me if the number i wind up with, is rational, or not? certainly, it IS computable.

there is a near-paradox with real numbers: in theory, every/any single (given) one of them is computable (just use its decimal expansion), but the entirety of them is not. even using clever methods like godel encoding, and diagonalization arguments, we just obtain increasing towers of "larger" sets of real numbers, all of which have a built-in achilles' heel.

to make matters worse, it is (to the best of my knowledge) unknown whether or not "the set of all real numbers" is actually a valid set given only the ZFC axioms. the reason being: if ZFC has a model, it has a countable model, and we have no way of knowing (as of now) "which" model we should take to be the "standard" one. it seems reasonable to insist we would prefer the "uncountable model" (we do so appreciate the sup/inf property of the reals), but there may be no logical defense for this (which might only bother a few people, we could just after all, adopt an "axiom of uncountability" in analogy with the axiom of infinity).

so...my guess is that there is still a lot of work to be done in investigating "kinds" of transcendental numbers, all of it rather difficult.

- #5

lavinia

Science Advisor

Gold Member

- 3,237

- 624

pi is certainly computable, but there's no discernable pattern in the digits themselves (that is, pi itself is suitable for use as a (pseudo-) random number generator).

does there exist an algorithm for computing the n-th digit of pi, BESIDES computing pi to n digits and looking it up?

i think determining "which" irrational numbers have "predictable" digit patterns is a very deep, and unsolved (hard) question, related to the difficulty of determining if a given real number is even irrational (or even worse, transcendental).

for example: suppose i take...√2, for example, and i construct a real number between 0 and 1 in the following way:

the first decimal digit of √2 is 4, so i take the 4-th digit of the decimal expansion of pi, which is 5:

0.5......

the second decimal digit of √2 is 1, so i take the "next" digit of pi's decimal expansion:

0.59......

the third decimal digit of √2 is 4, so i take the 9-th digit of the decimal expansion of pi, which is 3:

0.593.....

can you tell me if the number i wind up with, is rational, or not? certainly, it IS computable.

there is a near-paradox with real numbers: in theory, every/any single (given) one of them is computable (just use its decimal expansion), but the entirety of them is not. even using clever methods like godel encoding, and diagonalization arguments, we just obtain increasing towers of "larger" sets of real numbers, all of which have a built-in achilles' heel.

to make matters worse, it is (to the best of my knowledge) unknown whether or not "the set of all real numbers" is actually a valid set given only the ZFC axioms. the reason being: if ZFC has a model, it has a countable model, and we have no way of knowing (as of now) "which" model we should take to be the "standard" one. it seems reasonable to insist we would prefer the "uncountable model" (we do so appreciate the sup/inf property of the reals), but there may be no logical defense for this (which might only bother a few people, we could just after all, adopt an "axiom of uncountability" in analogy with the axiom of infinity).

so...my guess is that there is still a lot of work to be done in investigating "kinds" of transcendental numbers, all of it rather difficult.

Thanks for this interesting response.

I do not know anything about logic and models. What does it mean to say that the real numbers have a countable model?

Mathematicians talk about categories which are maybe logically problematic since they are often not sets. The category of vector spaces or topological spaces is way larger than any set. Still no problems seem to come from this.

I also know nothing of the theory of algorithms for computing numbers. But what about geometric constructions? For instance construction the square root of 2 as the diagonal of a square. Is that an algorithm?

- #6

- 86

- 0

this thread is really close to asking what a number is.

- #7

- 795

- 7

A formula to give the n-th digit of pi without needing to calculate the preceding digits was discovered in 1995. It only works in base-16, but it's still impressive that any such algorithm exists.i'm not sure if the computable numbers are what lavinia is after.

pi is certainly computable, but there's no discernable pattern in the digits themselves (that is, pi itself is suitable for use as a (pseudo-) random number generator).

http://en.wikipedia.org/wiki/Bailey–Borwein–Plouffe_formula

I agree with you that pi "looks" random and .101001000... doesn't. But pi isn't random. It might be normal, perhaps that's another area the OP might look into.

I don't believe that's correct. You can't just use the decimal expansion without listing it out in full ... which would take a countably-infinite string. Computability says that you need a finite-length string to defined an algorithm to compute the given number.there is a near-paradox with real numbers: in theory, every/any single (given) one of them is computable (just use its decimal expansion),

Since there are only countably many finite-length strings (hence countably many possible algorithms) but uncountably many reals, almost all reals are computable. The computable reals are countable, as are the definable reals and any other formulation of reals characterized by being describable using a finite-length string.

But still, I do agree that pi "looks random," even though it's computable. Other than normality, I'm not sure what class of numbers look random. Pseudo-random perhaps.

Since pi is not known to be normal, how can we be sure it's even pseudo-random, ie useful as a random number generator?

Last edited:

- #8

- 218

- 1

I don't really follow you, I'm probably missing something :)

Just to answer your first question "does there exist an algorithm for computing the n-th digit of pi, BESIDES computing pi to n digits and looking it up?" there actually is such an algorithm :Bailey Borwein Plouffe formula

But I don't think this as any say on computability of numbers and certainly not about rationality.

(By this I mean that, being able to compute some n'th digit of a number *as is* (without prior knowledge of the previous digits) probably does not have anything to do with the easyness of the computability of the number as the result of some infinite sums or whatever (on the other hand, it seems trivial to me that in fact, if you are willing to cheat, having an algorithm to compute a number to infinite precision implies that you can create a derived algorithm that gives you the nth digit by cheating, the problem is that this cheating would be so hard to measure (with abstract definitions of algorithms of arbitrary sizes) that it probably is not so useful to dig in this direction))

Your next question is weirder, you compute a number with an arbitrary rule that plays with decimal expansions of √2 and ∏ to create a new number.

Yes it is most certainly computable, but being computable is not related at all with being 'some sort of rational'

It would be hard to prove that Deveno's number is not a rational number but I am fairly certain it is not

As for rationality: a rational number is called this way by its virtue of being the ratio of two integers (that can be of any *finite* gigantic size you wish)

it is a direct consequence of this definition that its decimal (it doesn't have to be decimal, it could be any basis) expansion will have an infinite *repeating* pattern (if you take 0000.... as part of it (or it will be finite if you don't))

There is nothing else to this 'pattern thing' so to speak. if you create a pattern that 'looks simple' but is not an exact repetition forever, then it is just not a rational number.

You may want to classsify the toughness of the patterns so as to create some sort of intermediate categories of computable (but not rational) numbers but I don't think that would lead you very far.

For instance, Pi is such a number since the algorithm you were asking for does exist. the 'pattern' just happens to be a bit more involved than some other more trivial examples, but I really don't think that sets those numbers appart.

Pardon me if I completely missed your point, I am aware it is quite likely

Cheers...