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?


I wonder if certain relation of this type,may give us algebraic structure on LxQ set. When the answer is yes, we may ask if TM will stop his computation for every data for example. Of course there are is in some way trivial examples of such transition function T. But suppose what if structure generated by T' is much more complicated for example if it is lattice. I suppose in certain situations it may be not trivial ( trivial one is when You have STOP and START as bounding extrema, and all other states are at the same level) So when it occurs, TM has certain and nontrivial data flow through it graph of states. And structure of it ( eg. lattice) may give us a tool for proving specific properties.

  • 1
    $\begingroup$ Can you provide a little motivation as to why this would be of interest? $\endgroup$ Mar 8, 2011 at 8:52
  • 2
    $\begingroup$ Crosspost at MathOverflow: mathoverflow.net/questions/57791/… $\endgroup$ Mar 8, 2011 at 9:09
  • $\begingroup$ I am just curious. I am an amateur not affiliated on any institution. But whilst I am reading many things, I do not find any research on this area. Maybe it is somehow interesting? Maybe someone will start it? Or maybe it is well known area and I will learn something new;-) $\endgroup$
    – kakaz
    Mar 8, 2011 at 10:00
  • 2
    $\begingroup$ Perhaps your question can be phrased in a different way. Rather than asking whether the TM generates some algebraic structure, impose some algebraic structure on the state set/transition function, and ask what the consequences of this are. Also, avoid cross-posting your question. $\endgroup$ Mar 8, 2011 at 14:22
  • 1
    $\begingroup$ Here is a discussion of the policy on cross-posting: meta.cstheory.stackexchange.com/questions/225/… . In short, post on one site and if you do not receive an answer after some reasonable amount of time, post to the other site, stating explicitly that you are cross-posting. $\endgroup$ Mar 8, 2011 at 15:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.