4
$\begingroup$

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$, then it 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,R \} $ 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,\ldots,N $, $ j \in \{ L,R \} $ and $ q_{0L} =q_{0R} =START $, $ q_{NL} =q_{NR} =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,R \}$

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,R \} $ ?

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$,

(II) $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 the set $L \times Q$. 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.

Example of machine for which $T(q_{ij},a_{k}) = (q_{mn} , a_{l} ) $ and $k \leq l $ alt text

On this machine You may see, that there are loops in internal states ( no order in set Q defined by $T(q,a)$ ) however there is order in set $L = \{ 0,1,X,Y,B \}$. The state of the machine is bounded but its "diagram of execution" as graph depicting flow of internal states $q_i$ during execution may contain loops. Picture is scanned from Hopcroft, Ullman "Introduction to Automata theory, languages and computation." page 175 in Polish edition

Improve this question
$\endgroup$
5
  • $\begingroup$ Cross posted on CSTheory stackexchange: cstheory.stackexchange.com/questions/5346/… $\endgroup$
    – supercooldave
    Commented Mar 8, 2011 at 9:21
  • $\begingroup$ What kind of answer are you seeking? Such a TM cannot be universal, for example, since computation must stop very quickly. And the halting problem for such machines will be decidable, and even polytime decidable, for the same reason. $\endgroup$
    – Joel David Hamkins
    Commented Mar 8, 2011 at 11:57
  • $\begingroup$ @Joel David Hamkins - I am just curious if such class of TM is interesting. And I would be glad to see any reference on it. It is just free idea... "And the halting problem for such machines will be decidable" - is is about machines with (II) property or for more general machines set for which T(q,a) generates lattice (or possibly other algebraic) structure? $\endgroup$
    – kakaz
    Commented Mar 8, 2011 at 12:53
  • 1
    $\begingroup$ Kakaz, if the transition induces a partial order, then the machine cannot find itself in the same local configuration again after leaving it, since a partial order has no loops. It follows that the length of the whole computation is bounded by $|Q\times L|$, and so by running the computation for that long, you can solve the halting problem. Thus, these machines are very weak in computational power. $\endgroup$
    – Joel David Hamkins
    Commented Mar 8, 2011 at 13:34
  • $\begingroup$ @Joel David Hamkins - Thank You a lot! So in general it suggest that this class of machines is equivalent to TM without loops. If You think it is worth to write Your comment as answer I will accept it. $\endgroup$
    – kakaz
    Commented Mar 8, 2011 at 13:53

1 Answer 1

Reset to default
3
$\begingroup$

If the machine transition induces a partial order, then the machine cannot find itself in the same local configuration again after leaving it, since a partial order has no loops. It follows that the length of the whole computation is bounded by $|Q\times L|$, and so by running the computation for that long, you can solve the halting problem. So the machines are very weak in computational power.

The case of lattices is a special case of this, since a lattice is a special kind of partial order.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Although I agree that "machine cannot find itself in the same local configuration again" it is worth to note hat there stil may be loop in the state space of machine. Example of such machine You may find in Hopcroft, Ullman "Introduction to Automata T., Languages and Computation". on page 175 in Polish edition there is an example of simple machine for which there is relation T(q_i,a_k) = (q_j,a_s) and k<= s. Even so machine perform loop in its internal states. So the class of such machines may be still not trivial but of course they are bounded as You wrote. See above. $\endgroup$
    – kakaz
    Commented Mar 8, 2011 at 17:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .