This question is related to this one [Do Turing Machines generates any nontrivial lattice on the set o symbols or states?][1] The Turing machine (TM) is an abstract model for effective implementation of (finite algorithmic) calculation. TM is defined over some alphabet of symbols L and reading data performs a finite sequence of operations on these symbols in the manner described a kind of mapping, let's call it the transition mapping. TM has a certain inner state q which may be one element of a finite set Q. Transition mapping T specifies that if the machine reads in the current cell the symbol x from L.changes it to a symbol x ', and next data would be read from right (R) or left (L) cell. During this operation the state machine will change q to q '. We say that TM is defined as structure $ TM(L,Q,T, \{ START \}, \{ STOP \} ) $. But for this discussion it would be easier to say that we define certain sets as $ L'= L + \{ L,P \} $ and $ Q' = Q + \{ START,STOP \} $ and then we obtain "symmetric" $ T`: L' \times Q' -> L' \times Q' $. Then we omit any primes when it possible, and we define TM as $ TM(L,Q,T) $. We may describe states of TM as $ q_{ij} $ where $ i = 0...N $, $ j = L,P $ and $ q_{0L} =q_{0P} =START $, $ q_{NL} =q_{NP} =STOP $. Transition function is defined such that for given $ q_{ij} $ and symbol $ a_k $ from alphabet $ L $ machine in state $ q_{ij} $ reads $ a_k $ and goes to state $ q_{nm} $ and writes symbol $ a_s $ on the tape. That is: $ T'(q_{ij}, a_k) = T(q_i, a_s,) = (q_n, a_s, x) $ where $a_k, a_s \in L $ and $x \in \{ L,P \}$ > We may ask when $T(q_{ij}, a_k)$ > defines any ordering relation on $ L \times Q $ or on $Q$ or even on $ L \times Q \times {L,P} $ ? Of course in general there is no such possibility, but in certain situation we may for example has $T(q_{ij}, a_k)$ such that for any $j,k$, $T(q_{ij}, a_k) = (q_{ nm }, a_s)$ and $i \leq n $. In such situation T defines partial order. In such situation $ Q $ may be a lattice with relation generated by order generated by transition function T. > Are there any interesting facts about > TM with such (or similar) property? [1]: http://mathoverflow.net/questions/57675/do-turing-machines-generates-any-nontrivial-lattice-on-the-set-o-symbols-or-state *Info for an moderator: sorry but there is something wrong with latex rendering. I cannot obtain { for example. On Computer science it works but not there.*