We ask the question of how the Rees-Suskevitch theorem should be generalised to provide representations of orbit-finite 0-simple semigroups. We believe that orbit-finite groupoids will be useful for this.
Orbit-finite groups are finite, and therefore not very interesting from the perspective of sets with atoms. It turns out that orbit-finite groupoids form interesting structures. They will be useful in the study of orbit-finite semigroups in the following post.
Consider the following decision problem (for classical Turing machines). Let be a fixed, finite signature.
Input: Two orbit-finite relational structures , over .
Decide: is there a homomorphism from to ?
Question 1. Is the above problem decidable?
Observe that we are not asking for the existence of an equivariant homomorphism. If this were the case, the problem would be clearly decidable, since there are only finitely many equivariant homomorphisms between orbit-finite sets, and they can be effectively scanned. In this problem, the homomorphisms do not even have to be finitely supported! Below is an example where a homomorphism exists, but no finitely supported homomorphism exists.
Example. Consider the equality atoms. Let be the graph whose vertices are pairs of distinct atoms, and in which edges join a pair with its inverse. Let be the -clique. Then maps to , but no finitely supported homomorphism exists.
Following the idea of this post, in order to solve this problem, it might be useful to move to the totally ordered atoms .
Question 2. In the totally ordered atoms, if there is a homomorphism between orbit-finite structures , , is there one which is equivariant?
A positive answer to Question 2 would imply a positive answer to Question 1.
Edit. After reading Bartek’s comment below, I noticed that Question 2 has an even more negative answer. Consider the structures and (orders reversed). There is a homomorphism from to , namely the mapping , but there is none which is finitely supported.
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.
A result of Grädel and McColm shows that over finite structures, the logic DTCL is strictly less expressive than the logic TCL. My question is: can this result be translated into some separation result concerning Turing machines with atoms?
One research direction to consider is rewriting systems with orbit-finite sets of rules. There is a nice application to knot theory.