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 05:37:23 GMT

On Tue, 18 Jan 2005 20:43:03 +1000, |-|erc wrote:

> "Ed Murphy" <emurphy42@socal.rr.com> wrote in ...
>> 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.
>>
>>
> 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.

Relevant Pages

  • Re: The WHO CARES proof of anti-anti-diagonalisation
    ... Depending on how many people and how many flips per person, ... What exactly do you mean by sequence here? ... heads, the third person can flip tail tail then all heads, etc. ...
    (sci.math)
  • Re: probability puzzle
    ... only if the last n flips were all heads. ... What is the probability that the machine eventually halts? ... we count the length of the _trailing sequence_ of heads. ...
    (rec.puzzles)
  • Re: Universes...ad infinitum
    ... But we do need to keep in mind that there are ways of doing coin flips that aren't at all fair, ... This doesn't take away from the fact that existence is full of extremely unlikely events. ... Flip a coin 100 times and the sequence of heads and tails that you get is will be extremely unlikely, ...
    (uk.philosophy.atheism)
  • Re: No Unique Initial Segment And No Characteristic Expansion.
    ... H> Infinite people each flip coins infinite times. ... R>the number of people and the number of coin flips per person? ... H> Can you always find a different sequence of heads and tails? ...
    (sci.math)
  • Re: How many digits is pi computable to?
    ... if the maximum length of a sequence of coin flips is countably ... >> construct a sequence missed by a countably infinite number of people. ...
    (sci.logic)
Quantcast