Re: How many digits is pi computable to?

From: Ed Murphy (emurphy42_at_socal.rr.com)
Date: 01/18/05 

Date: Tue, 18 Jan 2005 10:11:47 GMT

On Tue, 18 Jan 2005 19:12:59 +1000, |-|erc wrote:

> "Ed Murphy" <emurphy42@socal.rr.com> wrote in ...
>> On Tue, 18 Jan 2005 15:32:40 +1000, |-|erc wrote:
>>
>> > Say you have an (countable) infinite set of people, and they only toss
>> > coins a finite number of times.
>> >
>> > <<sample>>
>> > P C
>> > 1 HTHT
>> > 2 HHTT
>> > 3 TTHH
>> > 4 TT
>> > 5 H
>> > 6 T
>> > ...
>> >
>> > they are given the constraint to only toss 4 times maximum.
>> >
>> > you can construct any sequence you want once I show you the list, but
>> > first you have to tell me how long your sequence is going to be?
>>
>> Oh, you're not giving *me* the 4-tosses-maximum constraint? Fine, then
>> my sequence will be 5 tosses. My sequence is HHHHH. None of your
>> people got *that* sequence, did they?
>>
>> Perhaps the orbital mind control lasers are interfering with your
>> ability to say what you mean in a precise fashion.
>
> that's fine, note that when competing against infinite other people you
> had to break their contraint.

Ah, now I see what you're attempting to stumble toward.

If the maximum length of a sequence of coin flips is finite, then the
number of possible sequences is also finite, and an infinite number of
people can choose them all.

However, if the maximum length of a sequence of coin flips is countably
infinite, then the number of possible sequences is *uncountably*
infinite. At this point, it is no longer adequate to refer simply to
an "infinite" number of people; we must specify either "countably
infinite" (in which case they cannot choose all possible sequences)
or "uncountably infinite" (in which case they can).

Here is a reiteration of the diagonal argument, which shows how to
construct a sequence missed by a countably infinite number of people.

If a set is countably infinite, then there is a function that maps
each element of that set to exactly one natural number. If the number
of people (other than me) is countably infinite, and the number of coin
flips per person is countably infinite, then the following functions
exist:

* A function f(P) that maps each person P (other than me) to exactly
  one natural number.

* For every person P (other than me), a function g_P(C) that maps each
  of their coin flips C to exactly one natural number.

* A function g_M(C) that maps each of my coin flips C to exactly one
  natural number.

Let f'() be the inverse of f(), g_P'() be the inverse of g_P(), and
g_M'() be the inverse of g_M().

I construct my sequence as follows:

For every natural number N,
find the Nth person P = f'(N),
find their Nth coin flip g_P'(N),
and set my Nth coin flip g_M'(N) opposite.

If any person P (other than me) chose the same sequence as me, then
let N = f(P); but then their Nth coin is different from my Nth coin,
contradiction. Thus no person P (other than me) chose the same
sequence as me. QED.

Relevant Pages

  • Re: Review of Mueckenheims book.
    ... ....2222, they are actually infinitely distant elements of a sequence, ... smallest positive number, on the infinite scale. ... That's the ordering used by Cantor to prove their countability. ... If a set S is countable, then there is a total order < of S such that ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... I have always allowed that sequences can be countably infinite, ... like the sequence of standard naturals is. ... TO nor anyone else has produced any axiom system in which it can be ... at several removes from pure mathematics, ...
    (sci.math)
  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... their output sequence. ... The fact is that an algorithm can also be used to ... first was about the probability of finding an apparent match. ... They may be matched within e at an infinite ...
    (talk.origins)
  • Re: Multiple infinities - one more look
    ... continued for lager length of digit sequences without limit. ... infinite digit sequences... ... so the resulting reals have an order. ... (i.e. having a finite program to output their digits in sequence). ...
    (sci.math)
  • Re: Calculus XOR Probability
    ... distances that make it a curve instead of a straight line, ... In the above sequence, n is a (strictly ... the diagonal is the "infinite case" of the staircases. ... closer to 2*pi as n -> oo. ...
    (sci.math)