5
$\begingroup$

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)?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Noah Schweber Jan 14 '15 at 19:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Benjamin Steinberg Jan 14 '15 at 19:37
  • 2
    $\begingroup$ 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? $\endgroup$ – Joel David Hamkins Jan 14 '15 at 20:16
5
$\begingroup$

Yes, there is now Pavlovic's characterization of Turing computability in terms of the monoidal computer, based on monoidal categories. http://arxiv.org/abs/1208.5205

$\endgroup$
  • $\begingroup$ Thank you for this answer. A related question: is there a much less technical account of some relationships between TM and algebraic concepts (monoids, etc.)? $\endgroup$ – user60665 Jan 30 '15 at 12:21
4
$\begingroup$

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.

The unbounded-search nature of projection will be absolutely required for any characterization of the c.e. sets, because there can be no computable bound on the length of time required to verify whether a given element is in a given c.e. set, for otherwise every c.e. set would be decidable, which would violate the unsolvability of the halting problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy