# Is there any research on Turing machines with transition relation homomorphic to given algebraic structure?

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.

1. For given structure of $$T(q_i,a_k)$$, are there any known facts about class of TM with that structure?
2. 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:

• The definition of TM is lacking many of the ingredients of TMs as I know them. For example, the TM transition relation is does not allows the head to move along the tape. See en.wikipedia.org/wiki/Turing_machine Commented Mar 9, 2011 at 16:03
• @Dave - Thank You fro remark. It is for simplicity here. Of course You may add a set of possible head moves - {L,R} as additional element of definition but we may simple assume that it is included in Q and is realized as information in internal state - see earlier questions. As regard to symmetry and homomorphism it is general enough. Commented Mar 9, 2011 at 20:26
• I cannot understand the question, but it does not seem that the question is about Turing machines. At least your definition of “Turing machine” is more like a definition of nondeterministic finite-state automaton (assuming that you really meant a relation instead of a function when you wrote “translation relation”). Commented Mar 9, 2011 at 22:56
• @Tsuyoshi Ito - please take a look on question from mathoverflow. There is simple example of TM for which following relation "let T(qi,aj) = (qk,as ), then froall i,j,k,s, j <= s " is satisfied. Such relation may be used for reasoning about machine execution or acceptance of certain language. This is generalisation of such reasoning. Probably thing You do not understand is notation here which is not standard but is simplified I presume without loss of generality. Commented Mar 10, 2011 at 7:28