<p>There are results about algebraic properties of languages (as opposed to the machines accepting the languages). For example, regular languages can be characterised using monoids. The Myhill-Nerode theorem relates an algebraic structure with the transition relation of a specific class of finite automata. You could look up those and subsequent results. </p>

<p>Rather than homomorphisms, bisimulation and simulation relations are the notion of choice for relating the structure of transition systems. Checking language equivalence between pushdown automata is undecidable but deciding equivalence of languages accepted by deterministic PDAs was open until 2001 when Gerard Sénizergues showed it was decidable. His proof uses algebraic ideas. Colin Stirling later gave a simplified proof (writeups and slides are available on his homepage). </p>

<blockquote>
  <p><em>Sénizergues, Géraud</em>, <a href="http://dx.doi.org/10.1007/3-540-63165-8_221" rel="nofollow noreferrer"><strong>The equivalence problem for deterministic pushdown automata is decidable</strong></a>, Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7--11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 671-681 (1997). <a href="https://zbmath.org/?q=an:1401.68168" rel="nofollow noreferrer">ZBL1401.68168</a>.</p>
</blockquote>

CC BY-SA 4.0
2011-03-10T04:08:52.430Z
2019-03-26T02:43:31.053Z
2019-03-26T02:43:31.053Z
Vijay D
<p>A Turing machine is defined as a structure <span class="math-container">$ TM(L,Q,T) $</span>, where <span class="math-container">$L,Q$</span> are sets of symbols and internal states of TM respectively, and T is a transition relation:</p>

<p><span class="math-container">$T: L \times Q \to L \times Q $</span> </p>

<p>for simplicity suppose that <span class="math-container">$Q$</span> contains all "terminal states" that is <span class="math-container">$ \{ START,STOP \} $</span>, and information about next move of the head on the tape, that is <span class="math-container">$\{L,R\}$</span> - it is just another information about internal state of the machine. <span class="math-container">$L$</span> contain all terminal symbols. This are finite sets. </p>

<p><em>This assumptions are for simplicity and easy notation, because full definition of TM is well known, and there is no need to explain it I presume. Please take a look for other questions below where such simplification is provided in more detailed way.</em></p>

<p><span class="math-container">$T$</span> is then a table with for example elements <span class="math-container">$Q$</span> in the column and elements of <span class="math-container">$L$</span> in  the rows. An element of such table is value of <span class="math-container">$T$</span> for its arguments that is:</p>

<p><span class="math-container">$T(q_i,a_k) = (q_j,a_s)$</span></p>

<p>Suppose that there is a homomorphism between <span class="math-container">$T(q_i,a_k)$</span> (as table) and certain finite algebraic structure (group, monoid, algebra, possibly some exotic structure). Or suppose that such transition relation has certain symmetries (for a stupid example here let me write: <span class="math-container">$T(q_i,a_k) = T(q_k,a_i)$</span>) or "subtables" with structure or symmetries homomorphic to given algebraic or other structure.</p>

<ol>
<li>For given structure of <span class="math-container">$T(q_i,a_k)$</span>,
are there any known facts about
class    of TM with that structure?</li>
<li>Are there any known equivalence
classes of <span class="math-container">$T(q_i,a_k)$</span> arising from algebraic
properties of <span class="math-container">$T(q_i,a_k)$</span> ?</li>
</ol>

<hr>

<p>Asking this question I follow the suggestion of  Dave Clarke. This is question related to following questions: </p>

<ul>
<li>asked here - <a href="https://cstheory.stackexchange.com/questions/5346/turing-machine-which-generates-order-on-the-set-of-its-states">Turing Machine which generates order on the set of its states</a> </li>
<li>asked on mathoverflow (and for which there is an answer by Joel David Hamkins) <a href="https://mathoverflow.net/questions/57791/turing-machine-which-generates-order-on-the-set-of-its-states">Turing Machine which generates order on the set of its states</a></li>
</ul>

CC BY-SA 2.5
2011-03-09T16:03:03.167Z
The definition of TM is lacking many of the ingredients of TMs as I know them. For example, the TM transition relation is does not allows the head to move along the tape. See http://en.wikipedia.org/wiki/Turing_machine
Dave Clarke
CC BY-SA 2.5
2011-03-09T20:26:09.613Z
@Dave - Thank You fro remark. It is for simplicity here. Of course You may add a set of possible head moves - {L,R} as additional element of definition but we may simple assume that it is included in Q and is realized as information in internal state - see earlier questions. As regard to symmetry and homomorphism it is general enough.
kakaz
CC BY-SA 2.5
2011-03-09T22:56:32.963Z
I cannot understand the question, but it does not seem that the question is about Turing machines.  At least your definition of “Turing machine” is more like a definition of nondeterministic finite-state automaton (assuming that you really meant a relation instead of a function when you wrote “translation relation”).
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-10T07:28:04.663Z
@Tsuyoshi Ito - please take a look on question from mathoverflow. There is simple example of TM for which following relation "let T(qi,aj) = (qk,as ), then froall i,j,k,s, j <= s " is satisfied. Such relation may be used for reasoning about machine execution or acceptance of certain language. This is generalisation of such reasoning. Probably thing You do not understand is notation here which is not standard but is simplified I presume without loss of generality.
kakaz
<reference-request><computability><turing-machines><algebra>
Is there any research on Turing machines with transition relation homomorphic to given algebraic structure?
kakaz
# Is there any research on Turing machines with transition relation homomorphic to given algebraic structure?

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

A Turing machine is defined as a structure $ TM(L,Q,T) $, where $L,Q$ are sets of symbols and internal states of TM respectively, and T is a transition relation:

$T: L \times Q \to L \times Q $

for simplicity suppose that $Q$ contains all "terminal states" that is $ \{ START,STOP \} $, and information about next move of the head on the tape, that is $\{L,R\}$ - it is just another information about internal state of the machine. $L$ contain all terminal symbols. This are finite sets.

*This assumptions are for simplicity and easy notation, because full definition of TM is well known, and there is no need to explain it I presume. Please take a look for other questions below where such simplification is provided in more detailed way.*

$T$ is then a table with for example elements $Q$ in the column and elements of $L$ in the rows. An element of such table is value of $T$ for its arguments that is:

$T(q\_i,a\_k) = (q\_j,a\_s)$

Suppose that there is a homomorphism between $T(q\_i,a\_k)$ (as table) and certain finite algebraic structure (group, monoid, algebra, possibly some exotic structure). Or suppose that such transition relation has certain symmetries (for a stupid example here let me write: $T(q\_i,a\_k) = T(q\_k,a\_i)$) or "subtables" with structure or symmetries homomorphic to given algebraic or other structure.

1. For given structure of $T(q\_i,a\_k)$,
   are there any known facts about
   class of TM with that structure?
2. Are there any known equivalence
   classes of $T(q\_i,a\_k)$ arising from algebraic
   properties of $T(q\_i,a\_k)$ ?

---

Asking this question I follow the suggestion of Dave Clarke. This is question related to following questions:

* asked here - [Turing Machine which generates order on the set of its states](https://cstheory.stackexchange.com/questions/5346/turing-machine-which-generates-order-on-the-set-of-its-states)
* asked on mathoverflow (and for which there is an answer by Joel David Hamkins) [Turing Machine which generates order on the set of its states](https://mathoverflow.net/questions/57791/turing-machine-which-generates-order-on-the-set-of-its-states)

**Tags:** reference-request, computability, turing-machines, algebra
> **Comments:**
> **username_1**: The definition of TM is lacking many of the ingredients of TMs as I know them. For example, the TM transition relation is does not allows the head to move along the tape. See http://en.wikipedia.org/wiki/Turing_machine  
> **username_0**: @Dave - Thank You fro remark. It is for simplicity here. Of course You may add a set of possible head moves - {L,R} as additional element of definition but we may simple assume that it is included in Q and is realized as information in internal state - see earlier questions. As regard to symmetry and homomorphism it is general enough.  
> **username_2**: I cannot understand the question, but it does not seem that the question is about Turing machines.  At least your definition of “Turing machine” is more like a definition of nondeterministic finite-state automaton (assuming that you really meant a relation instead of a function when you wrote “translation relation”).  
> **username_0**: @Tsuyoshi Ito - please take a look on question from mathoverflow. There is simple example of TM for which following relation "let T(qi,aj) = (qk,as ), then froall i,j,k,s, j <= s " is satisfied. Such relation may be used for reasoning about machine execution or acceptance of certain language. This is generalisation of such reasoning. Probably thing You do not understand is notation here which is not standard but is simplified I presume without loss of generality.  

---

## 1 answers

### Answer by username_3 on 2011-03-10. Score: 5

There are results about algebraic properties of languages (as opposed to the machines accepting the languages). For example, regular languages can be characterised using monoids. The Myhill-Nerode theorem relates an algebraic structure with the transition relation of a specific class of finite automata. You could look up those and subsequent results.

Rather than homomorphisms, bisimulation and simulation relations are the notion of choice for relating the structure of transition systems. Checking language equivalence between pushdown automata is undecidable but deciding equivalence of languages accepted by deterministic PDAs was open until 2001 when Gerard Sénizergues showed it was decidable. His proof uses algebraic ideas. Colin Stirling later gave a simplified proof (writeups and slides are available on his homepage).

> *Sénizergues, Géraud*, [**The equivalence problem for deterministic pushdown automata is decidable**](http://dx.doi.org/10.1007/3-540-63165-8_221), Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7--11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 671-681 (1997). [ZBL1401.68168](https://zbmath.org/?q=an:1401.68168).


---

