There are the so-called Miller machines (see my paper ). These are not quite Turing machines, but can be easily converted into Turing machines. It is defined by a collection of words $r_1,...,r_n$. The commands are $q\to r_i^{\pm 1} q$, $q\to aqa^{-1}$ where $a$ is a any letter of the alphabet, $q$ is the (only one!) state letter. Unlike a Turing machine, a Miller machine works with non-positive words which may contain inverses of the letters, and reduces a word after every step (these this is a particular cases case of the so-called S-machines). The word $w$ is accepted if the machine takes $wq$ to $q$. Clearly the set of words accepted bythe by the Miller machine is exactly the set of words equal to 1 modulo relations $r_i=1$. r_i=1$, $i=1,...,n$.
|
2 | added 98 characters in body | ||
|
|
||||
|
|
1 |
|
||
|
There are the so-called Miller machines (see my paper ). These are not quite Turing machines, but can be easily converted into Turing machines. It is defined by a collection of words $r_1,...,r_n$. The commands are $q\to r_i^{\pm 1} q$, $q\to aqa^{-1}$ where $a$ is a letter of the alphabet. Unlike a Turing machine, a Miller machine works with non-positive words and reduces a word after every step (these a particular cases of S-machines). The word $w$ is accepted if the machine takes $wq$ to $q$. Clearly the set of words accepted bythe Miller machine is exactly the set of words equal to 1 modulo relations $r_i=1$. |
||||
