Classification of standard alphabets

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.

One thought on “Classification of standard alphabets”

  1. This is related to an open problem: is the disjoint union of two standard alphabets always standard?

    I originally conjectured that the answer would be negative, and my hunch was that a counterexample should appear among alphabets of dimension 8. Łukasz’s thesis proves, among other things, that the hunch was wrong: the union of all standard alphabets of dimension 8 turns out to be standard.

    I do not know what to think of this anymore. Perhaps standard alphabets are closed under unions after all, but I have no idea how a proof might go.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>