Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83 (MC840302); site turing.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!unc!mcnc!decvax!linus!philabs!cmcl2!seismo!mcvax!turing!aeb
From: aeb@turing.UUCP
Newsgroups: net.math
Subject: Re: Beyond Exponentiation - What is the Ackermann Function?
Message-ID: <258@turing.UUCP>
Date: Tue, 12-Feb-85 18:13:30 EST
Article-I.D.: turing.258
Posted: Tue Feb 12 18:13:30 1985
Date-Received: Fri, 15-Feb-85 05:48:20 EST
References: <186@ihnet.UUCP> <616@spuxll.UUCP> <6318@boring.UUCP>
Reply-To: aeb@turing.UUCP (Andries Brouwer)
Organization: CWI, Amsterdam
Lines: 45
Apparently-To: rnews@mcvax.LOCAL

In article <6318@boring.UUCP> steven@boring.UUCP (Steven Pemberton) writes:
>In article <616@spuxll.UUCP> ech@spuxll.UUCP (Ned Horvath) writes:
>> I suggest you look at Ackermann's classic function, at least over the
>> naturals.  The first few "rows" of that function correspond roughly to "take
>> the successor", "add", "multiply", "exponentiate", etc.  The recursion is
>> (for n,m >= 0)
>> 
>> 	A(0, n) = n+1
>> 	A(n+1, 0) = A (n, 1)
>> 	A(n+1, m+1) = A (n, A (n+1,m))
>
>I have often seen this referred to as Ackermann's function, even in books,
>but I believe that it is actually Peter's function (with an acute accent
>over the first e), named after the late Rosza Peter of Hungary (with acute
>accent over the o), and that Ackermann's function is the following:
>
>	ack(x,y,n) {y>=0, n>=0}
>	  n=0 -> y+1
>	  y=0 and n=1 -> x
>	  y=0 and n=2 -> 0
>	  y=0 and n>2 -> 1
>	  n<>0 and y<>0 -> ack(x, ack(x, y-1, n), n-1)
>
>Can anybody confirm this for me?
>
Hartley Rogers jr., Theory of recursive functions and effective computability
gives the following definition for the 'Ackermann generalized exponential'
(on p.8, quoting Ro'sza Pe'ter, Rekursive Funktionen, Akade'miai Kiado',
Budapest, 1951):
	F(0,0,y) = y
	F(0,x+1,y) = F(0,x,y) + 1
	F(1,0,y) = 0
	F(n+2,0,y) = 1
	F(n+1,x+1,y) = F(n, F(n+1,x,y), y)
so that
	F(0,x,y) = x + y
	F(1,x,y) = x * y
	F(2,x,y) = y ** x
	...
Clearly F(n,x,y) = ack(y,x,n+1).

Das Fischer Lexicon Mathematik II calls the function A quoted above a
simplified version of the Ackermann Function due to Hermes.
-- 
      Andries Brouwer -- CWI, Amsterdam -- {philabs,decvax}!mcvax!aeb