Esta pregunta está relacionada con esta otra ¿Generan las máquinas de Turing algún entramado no trivial en el conjunto de símbolos o estados?
La máquina de Turing (MT) es un modelo abstracto para la implementación efectiva del cálculo (algorítmico finito). La MT se define sobre algún alfabeto de símbolos L y al leer los datos realiza una secuencia finita de operaciones sobre estos símbolos de la manera descrita un tipo de mapeo, llamémoslo mapeo de transición. TM tiene un cierto estado interno q que puede ser un elemento de un conjunto finito Q. El mapeo de transición T especifica que si la máquina lee en la celda actual el símbolo x de L.lo cambia por un símbolo x ', y el siguiente dato se leería de la celda derecha (R) o izquierda (L). Durante esta operación la máquina de estado cambiará q por q '. Decimos que la TM está definida como la estructura $ TM(L,Q,T, \{ START \}, \{ STOP \} ) $ . Pero para esta discusión sería más fácil decir que definimos ciertos conjuntos como $ L'= L + \{ L,R \} $ y $ Q' = Q + \{ START,STOP \} $ y entonces obtenemos el "simétrico" $ T`: L' \times Q' -> L' \times Q' $ . Entonces omitimos cualquier primo cuando sea posible, y definimos TM como $ TM(L,Q,T) $ .
Podemos describir los estados de la MT como $ q_{ij} $ donde $ i = 0...N $ , $ j \in \{ L,R \} $ y $ q_{0L} =q_{0R} =START $ , $ q_{NL} =q_{NR} =STOP $ . La función de transición se define de tal manera que para un determinado $ q_{ij} $ y el símbolo $ a_k $ del alfabeto $ L $ máquina en estado $ q_{ij} $ lee $ a_k $ y va al estado $ q_{nm} $ y escribe el símbolo $ a_s $ en la cinta. Eso es:
$ T'(q_{ij}, a_k) = T(q_i, a_s,) = (q_n, a_s, x) $
donde $a_k, a_s \in L $ y $x \in \{ L,R \}$
Podemos preguntarnos cuándo la relación de transición $T(q_{ij}, a_k)$ define cualquier relación de ordenación sobre $ L \times Q $ o en $Q$ o incluso en $ L \times Q \times \{ L,R \} $ ?
Otra pregunta más general es: cuando la relación de transición $T(q_{ij}, > a_k)$ define una estructura no trivial en $ L \times Q $ por ejemplo, no trivial ¿retículo?
Por supuesto, en general no existe esa posibilidad, pero en determinadas situaciones podemos por ejemplo tiene $T(q_{ij}, a_k)$ tal que para cualquier $j,k$ ,
(II) $T(q_{ij}, a_k) = (q_{ nm }, a_s)$ y $i \leq n $ .
En tal situación T define el orden parcial. En esta situación $ Q $ puede ser una red con relación generada por el orden generado por la función de transición T.
¿Hay algún dato interesante sobre TM con dicha propiedad (o similar)?
Observación/Motivación
Me pregunto si cierta relación de este tipo, puede darnos una estructura algebraica sobre el conjunto LxQ. Si la respuesta es afirmativa, podemos preguntarnos si TM detendrá su cómputo para cada dato, por ejemplo. Por supuesto, hay ejemplos triviales de tal función de transición T. Pero supongamos que la estructura generada por T' es mucho más complicada, por ejemplo, si es una red. Supongo que en ciertas situaciones puede no ser trivial (trivial es cuando usted tiene STOP y START como extremos, y todos los demás estados están en el mismo nivel) Así que cuando se produce, TM tiene cierto y no trivial flujo de datos a través de él gráfico de los estados. Y la estructura de la misma (por ejemplo, celosía) puede darnos una herramienta para demostrar propiedades específicas.
Ejemplo de máquina para la que $T(q_{ij},a_{k}) = (q_{mn} , a_{l} ) $ y $k \leq l $ 
En esta máquina se puede ver, que hay bucles en los estados internos ( sin orden en el conjunto Q definido por $T(q,a)$ ) sin embargo hay un orden en el conjunto $L = \{ 0,1,X,Y,B \}$ . El estado de la máquina está acotado, pero su "diagrama de ejecución" como gráfico que representa el flujo de estados internos $q_i$ durante la ejecución puede contener bucles. La imagen está escaneada de Hopcroft, Ullman "Introducción a la teoría de autómatas, lenguajes y computación", página 175 en la edición polaca
