Open Thread March 31 - April 7 2014

beoShaffer

If it's worth saying, but not worth its own post (even in Discussion), then it goes here.

Doesn't Cantor's diagonal argument prevent you from having a countable ordering of all the sequences?

There's no need for an enumeration of all the sequences, bayl na rahzrengvba bs gur rdhvinyrapr pynff gung gur cevfbaref frr gung gurl'er va jura gur ungf ner cynprq. Naq Bfpne_Phaavatunz'f fbyhgvba qbrfa'g arrq rira gung -- gur rdhvinyrapr pynffrf pna or nal genafsvavgr fvmr jungrire.

I'm now wondering whether for the case of two colours, there is a computable algorithm. A prisoner would apply the algorithm by feeding it an infinite tape listing all the colours of the hats, with a blank for his own, and the algorithm would in a finite time say what guess to make.

It seems unlikely. In a finite time it's impossible to get any idea whatsoever what equivalence class they're in, so the solution, if there is one, would need to be very different.

0Oscar_Cunningham12y

Idea for a proof: we could assume the warden chooses colours randomly for each prisoner, iid with probability a half. Then there might be a probabilistic proof that the puzzle is impossible. This proof would fail to rule out the true solution because gur frgf vaibyirq jbhyqa'g or zrnfhenoyr va gung pnfr, ohg gurl jbhyq or zrnfhenoyr va rirel pbzchgnoyr pnfr.

5

Open Thread March 31 - April 7 2014

5

If it's worth saying, but not worth its own post (even in Discussion), then it goes here.

5

5

Open Thread March 31 - April 7 2014

5

If it's worth saying, but not worth its own post (even in Discussion), then it goes here.

5