5
$\begingroup$

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:

Improve this question
$\endgroup$
4
  • $\begingroup$ 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 en.wikipedia.org/wiki/Turing_machine $\endgroup$
    – Dave Clarke
    Mar 9, 2011 at 16:03
  • $\begingroup$ @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. $\endgroup$
    – kakaz
    Mar 9, 2011 at 20:26
  • $\begingroup$ 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”). $\endgroup$
    – Tsuyoshi Ito
    Mar 9, 2011 at 22:56
  • $\begingroup$ @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. $\endgroup$
    – kakaz
    Mar 10, 2011 at 7:28

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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