Tag Archives: standard alphabets

papers

Classification of standard alphabets

1 Comment

The master thesis of Łukasz Wołochowski continues the study of standard alphabets and classifies  all alphabets of dimension up to 8, with regard to their standardness. Here is the thesis and here is its abstract:

This thesis concerns Turing machines with atoms. There exist alphabets with atoms over which Turing machines do not determinize and a method of alphabet classification is known. In this thesis we show and implement an improved version of this algorithm. The improvement is made by using advanced algorithms from the theory of Constraint Satisfaction Problems, as well as algebraic methods to reduce the size of a problem. As a result, we obtain a classification of all alphabets of dimension 8.

posts

Standard alphabets beyond equality atoms

Leave a comment

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 →