Compared to the usual treatises on recursion (eg, Rogers H. "Computability and Undecidability." McGraw-Hill, New York) the book of Samuel Eilenberg & Calvin C. Elgot "Recursiveness" treats such matters to the General context of free monoids (with finite base) instead of functions or relations between (finite) powers of natural numbers. As the strike theoretical elegance (typical of S. Eilenberg), the generalization requires its own hard case with respect to numerical orthodox one, is then to wonder about the scope and usefulness of this generalization.

¨ What is the benefit of this approach?

  • $\begingroup$ That is an awfully open-ended question. A little too discussion-y for my taste. (The quality of the English also makes this post difficult for me to parse.) $\endgroup$
    – Todd Trimble
    Oct 8 '11 at 16:04
  • 6
    $\begingroup$ "The recursive Samuel Eilenberg" makes for a great title for a novel. $\endgroup$ Oct 8 '11 at 16:19
  • 1
    $\begingroup$ Almost any non-identity permutation of the words in the title of this question would make more sense than the original. Voting to close. $\endgroup$ Oct 8 '11 at 16:36
  • 1
    $\begingroup$ +1 Mariano. Or perhaps for a short story by Borges. $\endgroup$
    – Todd Trimble
    Oct 8 '11 at 22:59
  • 1
    $\begingroup$ Can anyone parse this and correct it? I've tried but everything becomes very cloudy near the end. And I still can't make sense of the (otherwise masterfully poetic) title. $\endgroup$ Dec 25 '11 at 21:16

This is not really an answer but an attempt to clear away some of the underbrush and perhaps remove some confusion, so as to formulate the question in a more appropriate context.

As far as I can see, the question is simultaneously about two differences between Eilenberg's treatment of recursiveness and a traditional treatment in terms of (partial) functions whose inputs and outputs are just natural numbers. The first difference is not specific to Eilenberg, but rather is implicit in just about every treatment of traditional recursion theory. Even when one defines recursiveness in terms of functions on the natural numbers (as, for example, in Shoenfield's "Mathematical Logic"), one soon applies the notion to any sort of finite objects as inputs and outputs, for example, finite strings over a finite alphabet, or hereditarily finite sets. This change of context is usually accomplished by Gödel numbering, but there are also places where one or another of these alternative contexts is taken as the basic one. If I remember correctly, Shoenfield wrote a small book on recursion theory in which he took functions on strings as primitive, and Barwise's "Admissible Sets and Structures" undoubtedly takes functions on hereditarily finite sets as basic. These variations are essentially ignored in most situations because it is so routine to translate between them.

Now starting with a version of recursion theory based on strings, one can describe the step to Eilenberg's approach as shifting to a much more algebraic point of view. Of course, the set of strings on a finite alphabet is the free monoid on that alphabet, the monoid operation being concatenation. Eilenberg essentially develops the basics of recursion theory as a branch of monoid theory. I don't have his book handy, so I can't say how much he generalizes from free monoids to general monoids. [I disagree with the notion in one of the comments that Eilenberg's contribution is a generalization from the commutative monoid of natural numbers to non-commutative monoids; strings over non-singleton alphabets (and thus non-commutative free monoids) were in recursion-theoretic use for as long as there has been recursion theory --- maybe even longer, depending on how you view Post's production systems from the 1920's.]

I think I've finally arrived where I can ask a clear form of the original question: What benefits do we get from Eilenberg's algebraization of recursiveness in terms of monoids? Some people would consider it an advantage just to be able to say we're doing algebra rather than logic; needless to say, as a logician, I don't consider that a real advantage.

  • $\begingroup$ Thank you ANdreas Blass for your answere. Now I realize that isn't any theorical advantage (Eilenberg recursivity definitions is equivalent to "all what a Turing machine can do" about strings). I guess that Samuel Eilenberg did the recursivity theory in free monoid context (instead numerical as classical) because his project of bulding a theory of abstract machine and calculabulity, starting from automata that are strictly related to free monoids. $\endgroup$ Dec 26 '11 at 19:17

Your Answer

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

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