Another AC anomaly?
in [Logic]
|
From: Herman Jurjus on 23 Nov 2009 06:22 Has anyone seen this before? http://possiblyphilosophy.wordpress.com/2008/09/22/guessing-the-result-of-infinitely-many-coin-tosses/ I'm not sure yet what to conclude from it; that AC is horribly wrong, or that WM is horribly right, or something else altogether. In short the story goes like this: A game is played, in which infinitely many coins are tossed, and there's one player, who makes infinitely many guesses. Both are done over a finite period of time. The tosses and guesses are not made faster and faster, however, but slower and slower: at t = 1/n. There's no 'first' move. Claim: There exists a strategy with which you're certain to guess all entries correctly except for at most finitely many mistakes. Not 'certain' as in 'probability is 100%', but absolutely certain. Reasoning: On 2^w, consider the equivalence relation that makes x equivalent to y when x(n) =/= y(n) for at most finitely many n. Next, using AC, create a set S that contains precisely one element from every equivalence class. Strategy: at every move, you already know the results of the previous tosses, which is an infinite tail of some sequence in 2^w. Now take the unique element from S associated to that tail, take the n'th element of that sequence from S, and deliver that as your move. After some thinking, you will see that with this strategy, you're indeed certain to guess wrong at most finitely many times. Thanks, AC! Another nice mess you've gotten us into. -- Cheers, Herman Jurjus
From: David C. Ullrich on 23 Nov 2009 06:53 On Mon, 23 Nov 2009 12:22:17 +0100, Herman Jurjus <hjmotz(a)hetnet.nl> wrote: >Has anyone seen this before? > >http://possiblyphilosophy.wordpress.com/2008/09/22/guessing-the-result-of-infinitely-many-coin-tosses/ > >I'm not sure yet what to conclude from it; that AC is horribly wrong, or >that WM is horribly right, or something else altogether. > >In short the story goes like this: > >A game is played, in which infinitely many coins are tossed, and there's >one player, who makes infinitely many guesses. Both are done over a >finite period of time. The tosses and guesses are not made faster and >faster, however, but slower and slower: at t = 1/n. There's no 'first' >move. In case I'm not the only one who couldn't figure out exactly what's going on from that paragraph, the description on the page seems more clear: "For each n > 0, at \frac{1}{n} hours past 12pm the following is going to happen: aware of the time, you are going to guess either heads or tails, and then I am going to flip a coin and show you the result so you can see if you are right or wrong. This process may have to be done at different speeds to fit it all in to the hour between 12pm and 1pm." >Claim: >There exists a strategy with which you're certain to guess all entries >correctly except for at most finitely many mistakes. Not 'certain' as in >'probability is 100%', but absolutely certain. > >Reasoning: >On 2^w, consider the equivalence relation that makes x equivalent to y >when x(n) =/= y(n) for at most finitely many n. Next, using AC, create a >set S that contains precisely one element from every equivalence class. >Strategy: at every move, you already know the results of the previous >tosses, which is an infinite tail of some sequence in 2^w. Now take the >unique element from S associated to that tail, take the n'th element of >that sequence from S, and deliver that as your move. >After some thinking, you will see that with this strategy, you're indeed >certain to guess wrong at most finitely many times. > >Thanks, AC! Another nice mess you've gotten us into. I think the moral is not that AC leads to the weirdness but that this is a highly weird situation to begin with. At the time when we make any given guess we've already been told the result of infinitely many coin tosses... David C. Ullrich "Understanding Godel isn't about following his formal proof. That would make a mockery of everything Godel was up to." (John Jones, "My talk about Godel to the post-grads." in sci.logic.)
From: William Hughes on 23 Nov 2009 08:57 On Nov 23, 7:22 am, Herman Jurjus <hjm...(a)hetnet.nl> wrote: > Has anyone seen this before? > > http://possiblyphilosophy.wordpress.com/2008/09/22/guessing-the-resul... > > I'm not sure yet what to conclude from it; that AC is horribly wrong, or > that WM is horribly right, or something else altogether. > > In short the story goes like this: > > A game is played, in which infinitely many coins are tossed, and there's > one player, who makes infinitely many guesses. Both are done over a > finite period of time. The tosses and guesses are not made faster and > faster, however, but slower and slower: at t = 1/n. There's no 'first' > move. > > Claim: > There exists a strategy with which you're certain to guess all entries > correctly except for at most finitely many mistakes. Not 'certain' as in > 'probability is 100%', but absolutely certain. > > Reasoning: > On 2^w, consider the equivalence relation that makes x equivalent to y > when x(n) =/= y(n) for at most finitely many n. Next, using AC, create a > set S that contains precisely one element from every equivalence class. > Strategy: at every move, you already know the results of the previous > tosses, which is an infinite tail of some sequence in 2^w. Now take the > unique element from S associated to that tail, take the n'th element of > that sequence from S, and deliver that as your move. > After some thinking, you will see that with this strategy, you're indeed > certain to guess wrong at most finitely many times. > > Thanks, AC! Another nice mess you've gotten us into. > Note you can avoid AC, by defining a_n(m)= s(m) m>n, a_n(k) heads otherwise. The strategy is now to choose heads everytime. Note that this does not work. The problem is that although you use a_n to choose your guess for n, you do not use a_n for any guess for m>n. The fact that such a guess would be correct is of no use. If you could start the game with only a finite number of wrong guesses you are done. However, the game has no first move, so how do you start? - William Hughes
From: Herman Jurjus on 23 Nov 2009 09:03 David C. Ullrich wrote: > On Mon, 23 Nov 2009 12:22:17 +0100, Herman Jurjus <hjmotz(a)hetnet.nl> > wrote: > >> Has anyone seen this before? >> >> http://possiblyphilosophy.wordpress.com/2008/09/22/guessing-the-result-of-infinitely-many-coin-tosses/ >> >> I'm not sure yet what to conclude from it; that AC is horribly wrong, or >> that WM is horribly right, or something else altogether. >> >> In short the story goes like this: >> >> A game is played, in which infinitely many coins are tossed, and there's >> one player, who makes infinitely many guesses. Both are done over a >> finite period of time. The tosses and guesses are not made faster and >> faster, however, but slower and slower: at t = 1/n. There's no 'first' >> move. > > In case I'm not the only one who couldn't figure out exactly what's > going on from that paragraph, the description on the page seems > more clear: > > "For each n > 0, at \frac{1}{n} hours past 12pm the following is going > to happen: aware of the time, you are going to guess either heads or > tails, and then I am going to flip a coin and show you the result so > you can see if you are right or wrong. This process may have to be > done at different speeds to fit it all in to the hour between 12pm and > 1pm." > >> Claim: >> There exists a strategy with which you're certain to guess all entries >> correctly except for at most finitely many mistakes. Not 'certain' as in >> 'probability is 100%', but absolutely certain. >> >> Reasoning: >> On 2^w, consider the equivalence relation that makes x equivalent to y >> when x(n) =/= y(n) for at most finitely many n. Next, using AC, create a >> set S that contains precisely one element from every equivalence class. >> Strategy: at every move, you already know the results of the previous >> tosses, which is an infinite tail of some sequence in 2^w. Now take the >> unique element from S associated to that tail, take the n'th element of >> that sequence from S, and deliver that as your move. >> After some thinking, you will see that with this strategy, you're indeed >> certain to guess wrong at most finitely many times. >> >> Thanks, AC! Another nice mess you've gotten us into. > > I think the moral is not that AC leads to the weirdness but that > this is a highly weird situation to begin with. At the time when > we make any given guess we've already been told the result of > infinitely many coin tosses... Yup - it's a game without a first move. So 'weird' is an accurate qualification. Yet, it's not particularly difficult to give a mathematical description of the situation, reason about it, and convince ourselves that, mathematically, there's no problem with it. Ideally, it should be much harder to make mathematical sense of a game like this. That's why I included "WM is horribly right" as a possible moral. Apparently there's something wrong with backward supertasks (and not with ordinary, 'forward' supertasks). But why should that be? -- Cheers, Herman Jurjus
From: Herman Jurjus on 23 Nov 2009 09:09
William Hughes wrote: > On Nov 23, 7:22 am, Herman Jurjus <hjm...(a)hetnet.nl> wrote: >> Has anyone seen this before? >> >> http://possiblyphilosophy.wordpress.com/2008/09/22/guessing-the-resul... >> >> I'm not sure yet what to conclude from it; that AC is horribly wrong, or >> that WM is horribly right, or something else altogether. >> >> In short the story goes like this: >> >> A game is played, in which infinitely many coins are tossed, and there's >> one player, who makes infinitely many guesses. Both are done over a >> finite period of time. The tosses and guesses are not made faster and >> faster, however, but slower and slower: at t = 1/n. There's no 'first' >> move. >> >> Claim: >> There exists a strategy with which you're certain to guess all entries >> correctly except for at most finitely many mistakes. Not 'certain' as in >> 'probability is 100%', but absolutely certain. >> >> Reasoning: >> On 2^w, consider the equivalence relation that makes x equivalent to y >> when x(n) =/= y(n) for at most finitely many n. Next, using AC, create a >> set S that contains precisely one element from every equivalence class. >> Strategy: at every move, you already know the results of the previous >> tosses, which is an infinite tail of some sequence in 2^w. Now take the >> unique element from S associated to that tail, take the n'th element of >> that sequence from S, and deliver that as your move. >> After some thinking, you will see that with this strategy, you're indeed >> certain to guess wrong at most finitely many times. >> >> Thanks, AC! Another nice mess you've gotten us into. >> > > Note you can avoid AC, by defining > a_n(m)= s(m) m>n, a_n(k) heads otherwise. What's s(m) ? As a matter of fact, what's a_n(m) ? The game involves tosses and guesses, i.e. two sequences with one index: toss(n), guess(n). -- Cheers, Herman Jurjus |