100 hats puzzle, or, playing with the axiom of choice in the sand

[jack]

Puzzle the first, I assume you have heard this one, but I'll repeat it in case you haven't.

Suppose a hundred people are buried in the sand one in front of another so each can see all the people in front but none of the people behind. An Evil Dictator (TM) places a red or blue hat on each of them. He goes along the line from the back asking each person what colour their hat is, and at the end kills everyone who gets it wrong.

They're allowed to discuss strategy beforehand, but the dictator listens and doesn't allow them to come with any tone-of-voice signals or the like, information can only be conveyed by saying "red" or "blue" when asked.

What strategy is sure to save the most people? If the hats are colored randomly What strategy has the best Expectaion of number saved? For instance the first person is always at risk because NO-ONE knows anything about his hat at all, so no solution can do better than 99 guaranteed saved or 99.5 expected saved.

* You can save all the others. Agree a red/blue code where the first person calls odd/even for the number of red hats in front of him. Suppose the 2...n-1 people have been saved. Then the n'th person knows the of red hats behind him (because everyone just called the colours out aloud) and the number in front of him (because he can see them). The first person can also see the n'th person's hat, so if their count of red hats has the same even/oddness the n'th hat must be blue, else red.

Puzzle the second. What if the line was (semi) infinite?

* If you're willing to let die an infinite number, they can be as sparse as you like, the first, the googolplex'th, conway'th, the mindbogglinglybiggerthanthatth, etc. Just treat [1...googol-1] etc as many copies of the finite problem.

* To make things simpler, pretend the first guy doesn't have a hat and isn't killed. There's nothing you can do about him.

* If the sequence of hats eventually starts repeating you can save everyone: extrapolate the repeating sequence back to the first person (everyone can do this because they can see most of the repeating part) and consider the pattern of hats which differ from that. This is a finite number, so you can do the same trick as before, the first person calling out if the number of differing hats is odd or even, and everyone keeping count of the number behind them and then calling out the colour they expect unless they work out they must differ. (They have to remember the whole sequence because until it gets to them they won't know how many people were behind them, but it's possible if they think fast when it's their turn.)

* Treat red hats as 1 and blue as 0 and ignore the first one then they form a binary sequence n. If it's rational, it eventually repeats, so do the above thing. Otherwise it must uniquely represent a number between 0 and 1. What then? We can save everyone if we use the axiom of choice (who says it's useless :) )

Let x~y if x xor y is rational. This is an equivalence relation because r1^r2 repeats (with a product/lcm of the periods), so we can partition all sequences by it. From each class choose a representative x. Everyone can work out the x corresponding to n because if you change n by a finite number of digits (those behind the guy in the hat) it still ~n so has the same representative x.

Now consider n^x. This is rational, and you know a digit in it iff you know that digit in n, so use the same strategy as before counting those hats which differ from a x^n' where n' is a the repeating part of n extrapolated backwards.

* Can you do it without Choice? I bet you can't but I haven't proved it.

* If you don't have choice, can you manage a finite *expected* deaths?

Comments

[simont]

I read this paper some years ago, which is entirely based on the idea that if you can specify the choices to be made by a consistent rule then you don't need the AoC to assert the existence of the result of that choice-making. So you don't need AoC to assert the existence of (say) the set of even integers, obtained by "choosing" the lower element from each of the disjoint sets {0,1}, {2,3}, {4,5} etc. But you would need AoC in a situation where there was no pre-defined rule you could usefully pick.

Picking one real from each of your "rational difference" equivalence classes is such a problem; it would become a non-AoC-requiring operation if we had a well-ordering of the reals to appeal to, but constructing a well-ordering of the reals itself requires AoC.

[cartesiandaemon.livejournal.com]

Ooh, I like that. A maths paper with a gentle sense of humour. Isn't the difference most neatly illustrated by the socks/shoes example? You can give a set containing one each of infinitely many pairs of shoes: choose the left ones. With socks, you can only do so with AC.

(You have a set of pairs of shoes, a function "take the left" you can easily define, and an axiom "mapping of a set under a function is a set". The function is very easy, in their paper the function is hard.)

But here we're turning the flaw in the AC on its head. Normally it's a problem that you have no idea *which* matching you may get, the axiom just asserts that there is one. But we suppose we can actually find one, and furthermore that it's random and so can be used for cryptography, right?

[cartesiandaemon.livejournal.com]

I had another problem, unrelated to this conversation but about your machine. It should be able to simulate itself, shouldn't it? So it should be able to solve its halting problem simply by trying. But the same reasoning as normal should show that's impossible. What am I not seeing?

Does something horrible happen when you nest infinity instructions really deep?

I thought of this wondering what problems were on the cusp of solvability for an IM, and hence conceivable candidates for being possible to do but not undo.

[simont]

Hmm. Yes, the IM can simulate itself at full speed, or even faster; given any program which runs at the IM's basic clock rate (perhaps with subinfinities), you can simulate the whole thing within an infinity instruction and look to see whether it halted at the end.

int H(data P, data I) {
    int halted = 0;
    infinity {
	simulate P given input I;
	halted = 1;
    }
    return halted;
}

So yes, you could construct the classic Halting Problem counterexample:

void C(data P) {
    if (H(P, P)) {
	while (1);
    }
}
printf("%d\n", H(C, C));

and see what it produced.

If you tried this, then it would immediately start an infinite run in which it simulated itself; that in turn would immediately start a subinfinity doing the same thing, and so on. But of course, this being the Infinity Machine, that tight loop would run to infinitely many levels and then finish. So you're back to the original question about flipping the light switch infinitely many times: the output memory location would have to end up in an indeterminate state, and hence the answer would be undefined (or random, if we adopt the cryptographically extended Machine definition; or the tester would throw an exception, if you ran it inside an environment which policed the reading of indeterminate memory).

I think that's our get-out: the fact that it's possible for the Infinity Machine to generate an indeterminate value during normal running means that there's a whole class of programs whose halting behaviour is fundamentally nondeterministic because it depends on such a value, and hence they give an indeterminate result (or an exception) when run through the obvious halting tester. So all the nasty recursive cases that usually bring the HP crashing down simply get lumped into this category of "well it was doom anyway".

[simont]

Which means, thinking a bit further, that really on the Infinity Machine you don't want the above halting-problem tester H which returns true or false; you want an improved tester H2 which actually detects this sort of thing internally and returns true, false or nondeterministic. At which point, if you try to construct a counterexample program for which returning either of true or false would be self-contradictory, the tester will simply return nondeterministic, thumb its nose at you, and say "Yes? What's your point?".

I suppose that means you then have to construct a slightly different evil counterexample:

void C(data P) {
    switch (H2(P, P)) {
      case true:
	while (1);
      case nondeterministic:
	break;
      case false:
	/* make an indeterminate */
	infinity {
	    while (1) {
		i = 0;
		i = 1;
	    }
	}
	if (i)
	    while (1);
    }
}

which takes all three of those cases into account and permutes them, thus attempting to achieve a similar paradox covering them all. But I think running this through H2 would still return nondeterministic without paradox, not because the third case of the above switch was reached in the outermost invocation, but because the whole thing went fundamentally screwy!

[cartesiandaemon.livejournal.com]

Ah, yes, doh! I had a similar program, but forgot that we'd neatly circumvented the paradox by having more than two options.

OTOH, what if memory states that are edited infinitely often return 0? Is that deterministic or do you still get the light bulb paradox[1].

[1] I really wish I was the guy illustrating the paper of the guy who invented that ;)

[simont]

Hmmmsomemore. Now I'm having second thoughts about my entire argument.

The interesting thing about nesting infinite runs infinitely deep is that it permits you to have a sequence of machine instructions which is backward infinite and causally connected, i.e. for each instruction in the sequence there is a prior instruction whose result it can depend on. The original Infinity Machine (with only one level of nesting) could only have forward infinite runs.

With forward infinite runs only, the worst difficulty you get is the light switch paradox, which you can (a) solve by positing an arbitrary result in any such memory bit, and (b) detect at run time by having the Machine emulate itself at full speed and track whether each memory location is modified infinitely many times or not.

But with a backward infinite run, I think there's a whole new type of nondeterminism coming into play. Consider the following simple program:

int F(void) {
    int ret;
    infinity {
	ret = F();
    }
    return !ret;
}

This is precisely the light-switch paradox, but time-reversed, and I don't think the current definition of the Infinity Machine is adequate to specify what happens if you do this. No actual memory state has been edited infinitely often, so there's no nondeterminism of the type I've defined, and yet there are clearly two perfectly valid things that can happen when you run this function and no sensible way to choose between them.

(It's interesting to note here that forward infinite indeterminacy arises when there is no mathematically sound value for a bit of memory, and yet this is easily enough dealt with in the Machine's definition; but backward infinite indeterminacy arises when there is more than one such value, and yet seems harder to handle!)

I'm not even convinced that this can be detected reliably at run time in the way that forward infinite indeterminacy can be.

Perhaps one solution is to rule that the Infinity Machine is not permitted to nest infinite runs infinitely deep, or else some sort of exception happens. In which case, the answer to any Halting-Problem-destroying question is that you get that exception; so you now have a halting tester H3 with four return values: "halts", "does not halt", "halting is dependent on forward infinite indeterminacy", and "a backward infinite singularity occurred", with the last result coming up whether the singularity was built into the program under test or whether it occurred as a result of self-referential recursion.