= 27d567bc2d48d9f40e9ccc20ea370b15)
Manfred comments on Open Thread March 31 - April 7 2014 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (234)
Still confused. Richard Kenneway's solution relies on the true sequence being at a finite place in some ordering. 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.
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.
Proof that there is no sequences of algorithms A1, A2, ..., assigned to each prisoner, giving a winning strategy (assuming a computable warden given indices for the Ak):
Gur jneqra fvzhyngrf N-bar ba mreb mreb mreb... hagvy vg bhgchgf bar be mreb nsgre ernqvat x ovgf bs gur vachg. Gur jneqra gura cynprf gur bgure pbybe ung ba cevfbare 1, jub jvyy sbyybj N-bar naq thrff vapbeerpgyl; gur jneqra rafherf guvf ol cynpvat mreb ba cevfbaref gjb guebhtu x. Gur jneqra ercrngf guvf jvgu N-x+1 naq cevfbare x+1, fb gung x+1 jvyy thrff vapbeerpgyl. Naq fb ba. Fvapr rnpu Nx unygf nsgre ernqvat svavgryl znal ovgf sebz vgf benpyr, gur jneqra pna sbepr na vapbeerpg nafjre jvgu bayl svavgryl znal ovgf. Guvf jnl, gur jneqra pna sbepr vasvavgryl znal vapbeerpg nafjref. (Guvf eryngvivmrf gb nal benpyrf lbh pner gb tvir gb gur cevfbaref, nf ybat nf gur jneqra unf npprff gb gur pbhagnoyr wbva bs gubfr benpyrf.)