<p>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&#39;= L + \{ L,P \} $ and $ Q&#39; = Q + \{ START,STOP \} $ and then we obtain "symmetric" $ T`: L&#39; \times Q&#39; -&gt; L&#39; \times Q&#39; $. Then we omit any primes when it possible, and we define TM as $ TM(L,Q,T) $. </p>

<p>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:</p>

<p>$ T&#39;(q_{ij}, a_k) = T(q_i, a_s,) = (q_n, a_s, x) $ </p>

<p>where $a_k, a_s \in L $ and $x \in \{ L,P \}$</p>

<blockquote>
  <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} $ ?</p>
</blockquote>

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

<p>$T(q_{ij}, a_k) = (q_{ nm }, a_s)$ and  $i \leq n $. </p>

<p>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.</p>

<blockquote>
  <p>Are there any interesting facts about
  TM with such (or similar) property?</p>
</blockquote>

<p>Remark/Motivation</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-08T08:52:32.920Z
Can you provide a little motivation as to why this would be of interest?
Dave Clarke
CC BY-SA 2.5
2011-03-08T09:09:11.530Z
Crosspost at MathOverflow: http://mathoverflow.net/questions/57791/turing-machine-which-generates-order-on-the-set-of-its-states
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-03-08T10:00:36.290Z
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;-)
kakaz
CC BY-SA 2.5
2011-03-08T13:55:19.357Z
This question has its answer -  here: http://mathoverflow.net/questions/57791/turing-machine-which-generates-order-on-the-set-of-its-states in comment of Joel David Hamkins
kakaz
CC BY-SA 2.5
2011-03-08T14:22:08.093Z
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.
Dave Clarke
CC BY-SA 2.5
2011-03-08T15:20:27.193Z
@Dave Clarke: "Also, avoid cross-posting your question. " - could You explain me why? It is interesting to ask question here and on mathoverflow because in the set of people reading it do not overlap much - so asking it in that way gives larger probability of answer.  As regard to idea of asking in different way - yes You are right, there is many possible generalisations/changes in this idea. It seems to be very open, and fun. Take also a look into Joel David Hamkins on mathoverflow. I ask what if we change "order" into more general algebraic structure and require morphism only.
kakaz
CC BY-SA 2.5
2011-03-08T15:24:02.230Z
Here is a discussion of the policy on cross-posting: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231 . 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.
Dave Clarke
CC BY-SA 2.5
2011-03-08T15:30:38.883Z
My suggestion is to make the "more general algebraic structure" question an actual question, rather than some comment on another site.
Dave Clarke
CC BY-SA 2.5
2011-03-08T18:06:28.920Z
@Dave - Yes - it would be much more interesting, but I do not want to change question as it has accepted answer. However it is still interesting to discuss it in the whole generality in my opinion. I suggest to review crosspost policy, because if You are asking for example for references it would be a loss of time to do it in serial steps, and it is far much efficient to use some kind of parallel searching... Thank for Your remarks! Regards!
kakaz
CC BY-SA 2.5
2011-03-08T18:20:55.783Z
I'm suggesting that you post a new question.
Dave Clarke
CC BY-SA 2.5
2011-03-09T03:16:29.140Z
@Kakaz, please use meta to discuss policy issues, not here in the comments. You can find reasons for the policy in the meta post linked by Dave. Please also read the site's
[FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science) and [How to ask a good question?](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question).
Kaveh
<reference-request><turing-machines><lattice>
Turing Machine which generates order on the set of its states
kakaz
# Turing Machine which generates order on the set of its states

(Asked by: username_0 on 2011-03-08)

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?

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.

**Tags:** reference-request, turing-machines, lattice
> **Comments:**
> **username_1**: Can you provide a little motivation as to why this would be of interest?  
> **username_2**: Crosspost at MathOverflow: http://mathoverflow.net/questions/57791/turing-machine-which-generates-order-on-the-set-of-its-states  
> **username_0**: 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;-)  
> **username_0**: This question has its answer -  here: http://mathoverflow.net/questions/57791/turing-machine-which-generates-order-on-the-set-of-its-states in comment of Joel David Hamkins  
> **username_1**: 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.  
> **username_0**: @Dave Clarke: "Also, avoid cross-posting your question. " - could You explain me why? It is interesting to ask question here and on mathoverflow because in the set of people reading it do not overlap much - so asking it in that way gives larger probability of answer.  As regard to idea of asking in different way - yes You are right, there is many possible generalisations/changes in this idea. It seems to be very open, and fun. Take also a look into Joel David Hamkins on mathoverflow. I ask what if we change "order" into more general algebraic structure and require morphism only.  
> **username_1**: Here is a discussion of the policy on cross-posting: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231 . 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.  
> **username_1**: My suggestion is to make the "more general algebraic structure" question an actual question, rather than some comment on another site.  
> **username_0**: @Dave - Yes - it would be much more interesting, but I do not want to change question as it has accepted answer. However it is still interesting to discuss it in the whole generality in my opinion. I suggest to review crosspost policy, because if You are asking for example for references it would be a loss of time to do it in serial steps, and it is far much efficient to use some kind of parallel searching... Thank for Your remarks! Regards!  
> **username_1**: I'm suggesting that you post a new question.  
> **username_3**: @Kakaz, please use meta to discuss policy issues, not here in the comments. You can find reasons for the policy in the meta post linked by Dave. Please also read the site's [FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science) and [How to ask a good question?](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question).  

---

## 0 answers

