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

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?

Steven Pemberton, CWI, Amsterdam; steven@mcvax.