aeb@turing.UUCP (02/13/85)
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