NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/alt/folklore/computer/16670

Internet Message Format | 1992-11-23 | 3.1 KB

Path: sparky!uunet!haven.umd.edu!darwin.sura.net!ukma!cs.widener.edu!dsinc!ub!galileo.cc.rochester.edu!rochester!cornell!chapman
From: [e-mail] (Richard Chapman)
Newsgroups: alt.folklore.computers
Subject: Re: Ackermann's function
Keywords: Ackermann's function, recursion, primitive-recursive, FORTRAN, COBOL
Message-ID: <[e-mail]>
Date: 23 Nov 92 19:37:34 GMT
References: <ken.722284796@base>
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Lines: 52

[e-mail] (Ken C. Stewart) writes:

>Can anyone remind me (ahem) of the definition of Ackermann's function (a pair
>of mutually-recursive functions I think?)?

The Ackermann function:

    f(0,y)  = y + 1
    f(x+1,0) = f(x,1)
    f(x+1,y+1) = f(x,f(x+1,y))

>I saw it on the 'net years ago
>that it was one of the simpler examples of a recursive function that was not
>"primitive recursive", meaning, I think, that it could not be evaluated
>by iterative means, as the terminating condition for the loop to evaluate it
>depended on evaluating Ackermann's function ... I also seem to remember that
>since it required the programming language it was expressed in to support
>recursion, and since COBOL and FORTRAN (or at least some standard flavour
>thereof) don't, that COBOL and FORTRAN are not general purpose programming
>languages, whereas, say, vi macros are (see articles passim concerning
>Universal Turing Machine simulation using vi macros).

The Ackermann function is total recursive but not primitive recursive. The
primitive recursive functions are the smallest class of functions
containing the constant function f(x) = 0, the successor function f(x)
= x+1, projection functions for all arities to select each argument
(e.g.  a function of 4 arguments that returns its second argument),
and closed under the operations of substitution and recursion.

The proof that Ackermann is not p.r. is rather long, and is based on
showing that it grows faster than any p.r.  function.

If you augment the class of p.r. fun's by making it closed under the
operation of unbounded minimization (given a function, return the
least argument value for which that function returns zero) you get the
class of partial recursive functions, which is the same as the class
of Turing computable functions.

While recursion is not allowed in FORTRAN, you can implement it
yourself in a FORTRAN program by explicitly implementing a stack and
handling it all yourself. Now, whether or not FORTRAN has recursion
has little to do with the expressive power of the language; since
on-line storage and memory are finite, the most you can implement in
any language on any computer is a function that could be implemented by
a finite-state automaton (which is a far smaller class than the Turing
computable functions). However, barring the finite memory limit. If
you assume you have infinite memory size, and each location can hold
an arbitrarily large integer, all you need to implement all the
computable functions are: load a memory location with zero, increment
contents of a memory location, conditional jump, and transfer contents of one
memory location to another. All these are operations which FORTRAN and
COBOL are both capable of.