MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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$. 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\$.