Tag Archives: determinization of Turing machines

Standard alphabets beyond equality atoms

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 n one can compute the number of orbits of n-tuples of atoms. The following conditions are equivalent for every orbit finite set B.

  1. Turing machines over input alphabet B determinize
  2. There exists a function  f :B^* \to \set{0,1}^* 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 f.

Continue reading