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

Question

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.

http://en.wikipedia.org/wiki/Turing_machine http://en.wikipedia.org/wiki/Lattice_%28order%29

Answer 1

This reply only addresses part of what you ask. Asking these questions for finite automata may be illustrative. Given an automaton (Q,L,T,q, F) with states Q, alphabet set L, transition relation T, initial state q and final states F, one can ask if (Q,T) is a partial order. In general, the answer is no. If you want to order states based on transitions, one can ask if the (reflexive) transitive closure is a partial order.

It appears that you are asking about transition systems generated by an abstract machine. For pushdown automata and Turing machines, transitions are defined between configurations of the device. For the lambda calculus, transitions can be similarly defined. The operational semantics of an abstract machine defines the transition system it generates. Denotational semantics has a more order theoretic flavour.

Edit:(added later) It is common to study abstract machines using lattices. Instead of states, one uses the powerset of states. The transition relation gives rise to predecessor and successor operations on this lattice. Languages, transition graphs, transition sequences, both finite and infinite can be uniformly defined as fixed points of functions on such lattices. Fixed point characterisations open the door to order-theoretic analysis and are also the basis for many practical analysis methods in programming language and applied logic research.