In this post, I try to give a characterization of standard alphabets (i.e. alphabets where Turing machines determinize) which works for many choices of atoms.
Theorem. Assume that the atoms are oligomorphic, have a decidable first-order theory, and for every one can compute the number of orbits of -tuples of atoms. The following conditions are equivalent for every orbit finite set .
- Turing machines over input alphabet determinize
- There exists a function which is computable by a deterministic Turing machine, and such that two words are in the same orbit if and only if they have the same image under .