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]

Ooooh. I think that Choice technique might also be applicable to Infinity Machine cryptography; I think it allows the construction of a non-reversible "hash" function.

(I hadn't thought about the Infinity Machine in AoC terms before, but it seems clear that its design presumes the truth of the AoC.)

[simont]

Hmm, no, I tell a lie. That technique does permit the construction of a hash function which an Infinity Machine can't invert, but the downside is that you need uncountable memory to store the results of your AoC invocations, so an Infinity Machine can't compute the wretched thing either.

Still, that's progress; it's a step on the way to proving that workable IM hash functions aren't possible, which as a result of this thought experiment I think I'm now inclined to believe.

[cartesiandaemon.livejournal.com]

I'm too tired to think clearly atm, what is your hash function?

[simont]

Divide the space of infinite bit streams into equivalence classes such that two streams are equivalent iff their bitwise XOR is computable by a finitely long program. (Or "is eventually repeating", as in your example; but I don't think it makes much difference.) Then invoke the Axiom of Choice to find a representative member of each equivalence class. Then, given an input bit stream, you XOR it with the representative member for its own equivalence class, giving a computable infinite bit stream, which you can then convert into the finite program which generates it and then generate a hash bit by some ordinary finite hashing method of your choice. Repeat infinitely many times, with a fresh invocation of the Axiom of Choice for each output bit, and you have an infinitely long bit stream derived from your input one.

I believe even an Infinity Machine cannot invert this function, because taking into account any finite subset of the output bits does not narrow down the possible inputs to the point where they cease to be uncountable. So you can't invert it in any step-by-step manner: you have to hash an entire infinite stream in one go and just hope it comes out right, which it will with probability zero.

Unfortunately, as far as I can see, each invocation of the AoC requires uncountably many bits to store its output, and uncountably many instructions to be executed to invent it in the first place, so an Infinity Machine as I've described it cannot compute such a hash function either! And if you go one better and introduce an Uncountable Machine in order to compute the hash, then the enemy will have an UM as well and can easily enough invert the hash, simply by hashing every infinite bit stream!

[simont]

Of course, you could compute something like this with only an IM, if you made your AoC choices lazily: literally implement a random oracle, which is handed an (integer,sequence) pair and picks a random representative element of the sequence's equivalence class, unless it's already seen an equivalent sequence beside that integer in which case it returns the same representative element it returned last time.

I think that would work, but the downside is that the random oracle would have to be accessible to everyone who wanted to use the same hash function, and they'd all have to trust it with their plaintexts even though those plaintexts were precisely what they didn't trust one another with. So an intractable transfinite computation problem has been turned into an intractable trust problem, which isn't much of an improvement...

[cartesiandaemon.livejournal.com]

"So an intractable transfinite computation problem has been turned into an intractable trust problem, which isn't much of an improvement..."

ROFL.

[simont]

... and (I can't believe it's taken me ten hours to realise) if you were willing to have a centralised Infinity Machine implementing a random oracle, you could simply use that random oracle itself as your hash function and not have to faff about with equivalence classes at all. D'oh!

[cartesiandaemon.livejournal.com]

Yes, thank you.

Am I right, you're intending that the Choice is random, and the choice function is made public?

So if you had lots of infinite machines with that function built in as an extra you would have your hash computable? Of course, it's somewhat cheating to specify the ability of your machine so precisely, I think.

[simont]

Yes, the choice function (in fact countably many separate choice functions) would form part of the definition of the hash algorithm, and hence would have to be public.

And yes, I agree that if you bolted an oracle implementing those choice functions on to the side of the Infinity Machine then it would become able to compute but not break the hash function. However, I also agree that that would be an unconscionable level of cheating :-)

[cartesiandaemon.livejournal.com]

Is it equivalent to using choice to generate e_i, each taking each sequence to 0 or 1 randomly, and considering the sequence of ei of input?

[cartesiandaemon.livejournal.com]

So, in summary, thank you. I think I agree with your analysis but am still thinking about it.

[cartesiandaemon.livejournal.com]

Oooh, I got an oooh! :) *Does* IM need AoC?

[simont]

Well, it's certainly capable of doing things which would normally require AoC to justify in a mathematical derivation, such as inventing a countable stream of random bits. I suppose it needn't imply the full AoC, though, since there are plenty of AoC invocations which even it can't manage (such as the one you describe here!). So you could use it with only a cut-down AoC which limited its inputs.

[cartesiandaemon.livejournal.com]

Oh yes, doh! You invoked it pretty explicitely there when you said an infinite number of undefined bits would be random. But if they weren't, would it still need it?

Though, now I'm unsure. What does random even mean in this context? Is this something stronger than choice, since it'd satisfy the choice axiom to pick an unhelpful representative (eg. only ones whose hash was zero)?

[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.