# TM and abstract algebra

Usually, during lectures Turing Machines are firstly introduced from an informal point of view (for example, in this way: http://en.wikipedia.org/wiki/Turing_machine#Informal_description) and then their definition is formalized (for example, in this way: http://en.wikipedia.org/wiki/Turing_machine#Formal_definition).

Is it possible to give another 'equivalent' definition that relies more precisely on algebraic concepts (i.e. algebraic structures: semigroups, monoids, etc; just like, for instance, regular languages are recognized by finite monoids and context-free languages are recognized by a product of a free group and a finite monoid)?

• I think this question is potentially very interesting, but needs a lot of clarification: for one thing, what do you mean by "an algebraic structure?" For now I've voted to close as "unclear," but I'll happily retract that if the question is improved. OP, if you google around you'll quickly find many things of interest - for example, check out the lamplighter group, or papers such as sciencedirect.com/science/article/pii/S0304397508002326. – Noah Schweber Jan 14 '15 at 19:30
• Presumably he means that regular languages are recognized by finite monoids and context-free languages are recognized by a product of a free group and a finite monoid and so what recognizes an arbitrary recursively enumerable language. – Benjamin Steinberg Jan 14 '15 at 19:37
• The MRDP theorem shows that the c.e. sets are precisely the projections of the zero sets of multivariable polynomials over the integers. Is that the kind of thing that is wanted? – Joel David Hamkins Jan 14 '15 at 20:16

As I mentioned in the comments, it is a consequence of the MRDP theorem that the computably enumerable sets of natural numbers are precisely the projections of the natural-number zero sets of the multi-variable polynomials over the integers. That is, a set $A\subset\mathbb{N}$ is computably enumerable just in case there is a polynomial $p(x,\vec y)$ over the integers such that $n\in A$ just in case $\exists \vec m\in\mathbb{N}$ such that $p(n,\vec m)=0$. (One can equivalently work over $\mathbb{Z}$ rather than $\mathbb{N}$.)
Another widely used characterization of the c.e. sets is as the $\Sigma_1$-definable sets. These are the same as the projections (onto the first coordinate) of the primitive recursive or even the regular subsets of pairs of natural numbers. Thus, if you are willing to use your algebraic characterizations of regular subsets of the plane, then all you have to do is project onto the first coordinate to get the c.e. sets. This projection operation amounts to an unbounded existential quantifier: $a\in A$ just in case $\exists b\ (a,b)\in B$, where $B$ is a very simple subset of the plane.