Re: [FWP] Ackerman

["Daniel S. Wilkerson" <dsw@digital-integrity.com>]

Christer Ekholm wrote:

> Is Ackermann's function useful for anything?

According to my reading of "Introduction to Automata Theory, Languages, and
Computation" by Hopcroft and Ullman, (1979) p. 175 Ackermann's function is not
primitive recursive, but is recursive.  This is "useful" as it demonstrates the
seperation of the two classes of functions.

Also, if you think of Ackerman's function as a table, one row is constant, the
next row is the successor function on x, the next row is addition, the next
multiplication, the next exponentiation, the next tetration, etc.  So you can
see the natural sucession of these operations.

Useful for computing something?  Probably not, as the parts that can be
computed can be more easily expressed in more primitive ways, and the parts
that can't, well, can't.

Daniel


==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe