Second question, probably better: http://mathoverflow.net/questions/57791/turing-machine-which-generates-order-on-the-set-of-its-states
I would like to ask ( if it is not terribly obviously wrong):
- 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$? )
- 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$? )
- How different statements on the theory of computability translated into lattice theory looks like?
- Has anyone investigated this? Maybe someone knows some references?
What about similar construction for lambda calculus (where order may be generated by substitution sequence)?
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.