# Do Turing Machines generates any nontrivial lattice on the set o symbols or states?

Second question, probably better: Turing Machine which generates order on the set of its states

I would like to ask ( if it is not terribly obviously wrong):

1. Do Turing Machine generates nontrivial lattice structure on alphabet set $L$ or on the set of its states $Q$ or on its Cartesian product $Q \times L$? )
2. Is this mapping is unique? (Unfortunately, it seems that not in the case of $L$ or $Q$ alone. But maybe if we combine a set of states with a set of alphabet symbols $Q \times L$? )
3. How different statements on the theory of computability translated into lattice theory looks like?
4. Has anyone investigated this? Maybe someone knows some references?

What about similar construction for lambda calculus (where order may be generated by substitution sequence)?

Motivation:

I am in doubt whether it makes sense. Well, but now that so many have described, I will let it stay as is.

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 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 '.

Lattice is "a partially ordered set (also called a poset) in which any two elements have a unique supremum (the elements' least upper bound; called their join) and an infimum (greatest lower bound; called their meet)." STOP and START are both bound elements for all the other steps of TM computation. So in fact there is a graph depicting such "computation" flow on which START and STOP elements are minimal and maximal and which forms maybe a lattice.

During the operation of the machine goes through a set of states $START = q_0 -> q_i -> ... -> q_k-> q_N = STOP$. Elements of the START and STOP are a kind of extreme elements - the machine starts to work in the state of the START and never return to it, and it ends in a position to stop and it never goes out (if the calculations will be completed ). Of course there is possible trivial lattice defined with order as $START \leq q_i \leq STOP$ for any $i$. But it is not the only possibility, and usual flow diagram for computation states $q_i$ usually looks much more interesting an complicated.

-