Skip to main content
2 of 9
added 927 characters in body
kakaz
  • 1.6k
  • 2
  • 24
  • 35

Turing Machine which generates order on the set of its states

This question is related to this one Do Turing Machines generates any nontrivial lattice on the set o symbols or states?

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 transition relation $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} $ ?

Another, more general question is: when transition relation $T(q_{ij}, > a_k)$ defines nontrivial structure on $ L \times Q $, for example nontrivial lattice?

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?

Remark/Motivation

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.

Info for an moderator: sorry but there is something wrong with latex rendering. I cannot obtain { for example. On Computer science it works but not there.

kakaz
  • 1.6k
  • 2
  • 24
  • 35