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 .

1. Turing machines over input alphabet determinize
2. 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 .

Continue reading →