3 ms·
Nothing here is Turing computable because it's infinite, but telling what class you're in is the easy part. The class is just all assignments (player -> hat co
by less_less 4y ago
Nothing here is Turing computable because it's infinite, but telling what class you're in is the easy part. The class is just all assignments (player -> hat color) that are the same as what you see except in finitely many places.
The hard part is F, which maps each equivalence class to some member of the class.
- lupire 4y agoNot just infinite, but also uncountable. > The hard part Quite hard: Not computable, in fact.
- less_less 4y ago> Not just infinite, but also uncountable. If the players are countable and the colors are countable, then each equivalence class is also countable. I guess that might also make it computable, in some model that lets you deal with infinite objects? Eg suppose you have a 2-tape Turing machine where one read-write tape is input which records what you see. There is a separate tape for the Turing machine's internal state. The machine outputs an infinite stream of assignments by doing normal Turing machine things, plus a "yield" instruction that yields the current state of the input tape as an output. The equivalence classes ought to be computable in that model. Note that the equivalence class is a set, so the Turing machine's output should be interpreted that way, i.e. two equivalent inputs will give outputs in a different order. (They can't always give outputs in the same order, because F isn't computable.) But yeah, there are uncountably many equivalence classes, and F is not computable. If it were, then as I understand it, then you wouldn't need choice.