Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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

share|improve this question
    
Cross posted on CSTheory stackexchange: cstheory.stackexchange.com/questions/5346/… –  supercooldave Mar 8 '11 at 9:21
    
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. –  Joel David Hamkins Mar 8 '11 at 11:57
    
@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? –  kakaz Mar 8 '11 at 12:53
1  
In order to get {, double the backslash. Alternatively, and more generally, all sorts of trouble with math can be fixed by putting backticks around the whole expression. (I don't understand why this isn't done automatically. Why would anyone want to expand markdown syntax inside math expressions?) –  Emil Jeřábek Mar 8 '11 at 13:08
1  
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. –  Joel David Hamkins Mar 8 '11 at 13:34

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  kakaz Mar 8 '11 at 17:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.