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.
Consider the following decision problem, over the equality symmetry.
Input: an orbit-finite system of linear equations over
Decide: does have a solution (not necessarily finitely-supported)?
Inspired by Eryk’s beautiful solution of this problem, we present another solution, using an amazing theorem from topological dynamics.
It can happen that two equivariant sets with atoms are related by a finitely supported bijection, but not by an equivariant bijection.
There are several decision problems for certain computation models with atoms that are decidable when atoms admit certain well quasi order (WQO), and undecidable otherwise. We recall the problems and formulate few questions related to WQOs.
Čech cohomology is a way of defining cohomology groups (a topological invariant with algebraic structure) on a topological space. We give a rough description of the construction, in a very special case of a torus, and relate it to the construction of the nonstandard alphabets. Continue reading
A set is orbit finite if and only if the number of its elements supported by atoms grows polynomially with .