A Turing machine is defined as a structure $ TM(L,Q,T) $, where $L,Q$ are sets of symbols and internal states of TM respectively, and T is a transition relation:
$T: L \times Q \to L \times Q $
for simplicity suppose that $Q$ contains all "terminal states" that is $ \{ START,STOP \} $, and information about next move of the head on the tape, that is $\{L,R\}$ - it is just another information about internal state of the machine. $L$ contain all terminal symbols. This are finite sets.
This assumptions are for simplicity and easy notation, because full definition of TM is well known, and there is no need to explain it I presume. Please take a look for other questions below where such simplification is provided in more detailed way.
$T$ is then a table with for example elements $Q$ in the column and elements of $L$ in the rows. An element of such table is value of $T$ for its arguments that is:
$T(q_i,a_k) = (q_j,a_s)$
Suppose that there is a homomorphism between $T(q_i,a_k)$ (as table) and certain finite algebraic structure (group, monoid, algebra, possibly some exotic structure). Or suppose that such transition relation has certain symmetries (for a stupid example here let me write: $T(q_i,a_k) = T(q_k,a_i)$) or "subtables" with structure or symmetries homomorphic to given algebraic or other structure.
- For given structure of $T(q_i,a_k)$, are there any known facts about class of TM with that structure?
- Are there any known equivalence classes of $T(q_i,a_k)$ arising from algebraic properties of $T(q_i,a_k)$ ?
Asking this question I follow the suggestion of Dave Clarke. This is question related to following questions:
- asked here - Turing Machine which generates order on the set of its states
- asked on mathoverflow (and for which there is an answer by Joel David Hamkins) Turing Machine which generates order on the set of its states