Re: How many digits is pi computable to?

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

Date: Wed, 19 Jan 2005 08:48:28 GMT

On Wed, 19 Jan 2005 15:59:09 +1000, |-|erc wrote:

> "Ed Murphy" <emurphy42@socal.rr.com> wrote in message
>
>> >> >> > 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.
>> >>
>> >>
>> > How many flips of your 'new' coin sequence have other people done from
>> > flip 1 to flip X?
>>
>> I'm not sure what you're asking.
>>
>> For any finite X, there may well be a person whose first X flips are the
>> same as my first X flips. *However*, for any person other than me,
>> there is some finite X such that *that person's* first X flips are *not*
>> the same as my first X flips.
>>
>>
> antidiag = <HHHHTTTTHHHHTTTTHHHHTTTT..>
> |<------ How Many flips ? ------->|

I have been assuming "a countably infinite number". I'm not sure
whether it's meaningful for this number to be uncountably infinite.

> Infinite flippers
> 1 <THTHTHTHTHTHTHTHHTH..>
> 2 <TTHTHTHTTHTTHTHTTHTH..>
> 3 <THTHTHTHTHTTTHTTHTHH..>
> 4 <TTTTTHTHTHTHTHTHTHTH..>
> 5 <HHHHHHHHTTTTHTHTHTH..>
> ...

I have addressed both a countably-infinite and uncountably-infinite
number of flippers.

> Its not a hard question, remember John Savards comment
> " a random real number will be on it to an infinite number of digits"

I assume you are referring to Message-ID:
<41eb3f42.795692@news.ecn.ab.ca><354kurF4dasldU1@individual.net>

Problem is, John is also misusing "infinite"; he should have said
"arbitrarily large".

As I stated previously: For any arbitrarily large but finite N,
the first N digits of D (where D is the number constructed by the
diagonal argument) are matched. But D has an infinite number of
digits, and Infinity Is Weird, and you will bloody well be Wrong,
Wrong, Absolutely Brimming Over With Wrongability until you buckle
down and accept that and deal with it.

You have not succeeded in overturning the diagonal argument unless
you identify an element of the set that has *no* digits mismatched
with D. However, if the size of the set is countably infinite,
then the diagonal argument shows that every element of the set has
a digit that mismatches; and if the size of the set is uncountably
infinite, then the diagonal argument no longer places a claim on it.

To summarize:

P = number of people
C = number of coin flips per person

If P is countably infinite and C is countably infinite, then the
diagonal argument works.

If P is countably infinite and C is uncountably infinite, then the
diagonal argument still works. (Consider a countably infinite
subset of each person's sequence of coin flips. This case now
reduces to the previous case.)

If P is uncountably infinite, then the diagonal argument doesn't
work. (It relies on a bijection from the set of people to the
natural numbers; if P is uncountably infinite, then by definition
there isn't one.)

And now let's set aside all these side issues that may or may not
pertain, and revisit your original question. "How many digits is
pi computable to?" Or, to avoid digressions into practical physics,
and also to explicitly address the difference between countable and
uncountable infinities: "Does the complete decimal expansion of pi
consist of a countably or uncountably infinite number of digits?"

I don't know. Discuss.

Relevant Pages

  • Re: How many digits is pi computable to?
    ... >> the same as my first X flips. ... I have been assuming "a countably infinite number". ... whether it's meaningful for this number to be uncountably infinite. ...
    (sci.math)
  • Re: How many digits is pi computable to?
    ... >> the same as my first X flips. ... I have been assuming "a countably infinite number". ... whether it's meaningful for this number to be uncountably infinite. ...
    (sci.logic)
  • Re: Cantor and the binary tree
    ... to assume that one of these numbers becomes uncountably infinite while the other remains countably infinite. ... One can hardly imagine a simpler mathematical proof. ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... You are confusing arithmetic exponentiation and the cardinality of powersets - they are not the same thing, ... These are precisely the types of expressions I want to see distinguished, not all lumped together as if arithmetic becomes meaningless for infinite values. ... Since each term represents the number of points your mapping defines at each step, we conclude that your mapping defines only a countably infinite number of points in total. ... a countably infinite number of points, which is far too small to cover the reals. ...
    (sci.math)
  • Re: An uncountable countable set
    ... Tony Orlow wrote: ... infinite binary fractions in [0,1)). ... when represented as finite bitstrings. ... You agree that "Any countably infinite set of bit positions ...
    (sci.math)