The infinite prisoners with hats puzzle runs as follows. We have a countably infinite group of prisoners numbered $\{1, 2, \dots\}$, each of whom is wearing either a white hat or a black hat. The $n$th prisoner can only see the hats of prisoners $\{n+1, n+2, \dots \}$. A guard asks each prisoner successively, starting from the first, what the colour of their hat is. If the prisoner guesses wrong, they are executed on the spot. Assume that the prisoners cannot hear the answers of those who have been asked before them. Find a strategy for the prisoners that guarantees only finitely many are executed.
There is a standard answer using the axiom of choice (which is known to be necessary). Encode the hats as $0, 1$ and consider the following equivalence relation on the space of all countable sequences $2^\mathbb{N}$. Let $(x_i) \sim (y_i)$ if and only if there exists some $k \in \mathbb{N}$ such that $x_n = y_n\ \forall n > k$. In other words, two sequences are equivalent if they agree after some finite point. Choose a representative from each equivalence class - as each prisoner can see all but a finite number of hats, they know which equivalence class the line of prisoners falls under. Assuming a given prisoner knows that they are $n$th in line, they simply answer the $n$th element of the representative, and we have our solution.
It seems that this solution fails if the prisoners do not know where they lie in the line. Consider some sequence of hats $(x_i)$, and construct a new sequence $(y_i) = \{0, \dots, 0, x_1, x_2, \dots \}$ by padding some finite number of zeros to the front. In general, $(x_i)$ and $(y_i)$ will not lie in the same equivalence class and hence if a prisoner does not know what number they are in the line there is ambiguity as to which representative they must choose.
One could consider "patching" the solution by letting $(x_i) \sim (y_i)$ if there exist arbitrarily large subsequences on which they agree, but this allows for sequences of hats in which an infinite number of prisoners die:
$(x_i) = \{0, *, 0, *, *, 0, *, *, *, 0, \dots \}$
$(y_i) = \{1, *, 1, *, *, 1, *, *, *, 1, \dots \}$
where the sequences are defined to agree on the $*$ elements. I suspect that I am missing something obvious and there is an easy way to solve the case where the prisoners do not know their number in the line. Thoughts?
I think you can patch the argument in a different way, by declaring two sequences $(x_i)$ and $(y_i)$ equivalent if there exist integers $k$ and $N$ such that $x_{i+k} = y_i$ for all $i \ge N$, i.e., if you introduce shift equivalence. Now pick one element $(x_i)$ out of the equivalence class that you observe. If the tail $(x_i)_{i \ge n}$ does not uniquely determine your position in the sequence, this means that there exists $N$ and $k \ne 0$ with $x_{i+k} = x_i$ for $i \ge N$, i.e., that the sequence is eventually periodic. However, in that case for $n \ge N$ it does not matter which position the $n$-th prisoner picks, as long as it is in the periodic tail of the sequence, so again all but finitely many of them survive.