While working on a LISP programming excercise, I ran across the following
recursive function definition:
ACKERMAN'S FUNCTION
The function A operates on two arguments m,n
A(0,n)=n+1
A(m,0)=A(m-1,1)
A(m,n)=A(m-1,A(m,n-1))
Upon programming, I discovered that the definition is deceptive in its
simplicity. Specifically, does the function has a definition for all
possible m,n? Is there a more general function to describe this function?
etc....etc...
I am looking for information and references regarding Ackerman's function.
If anyone can help, send email to ·······@hamp.hampshire.edu
-andrew kriger
[ I directed followups to comp.lang.lisp as I don't follow comp.ai or
sci.math -rfb ]
In article <··················@hamp.hampshire.edu> ·······@hamp.hampshire.edu writes:
ACKERMAN'S FUNCTION
The function A operates on two arguments m,n
A(0,n)=n+1
A(m,0)=A(m-1,1)
A(m,n)=A(m-1,A(m,n-1))
Hopcroft and Ullman's
_Introduction_to_Automata_Theory,_Languages,_and_Computation_ (page
175) defines it slightly differently:
A(0,y)=1
A(1,0)=2
A(x,0)=x+2 for x >= 2
A(x+1,y+1)=A(A(x,y+1),y)
Specifically, does the function has a definition for all
possible m,n?
No, both parameters have to be greater than or equal to zero.
Is there a more general function to describe this function?
Not that I know of. Note that f(n)=A(n,n) is a classic example of a
*very* fast growing function. Also, a bit of analysis with a focus on
holding small values of the second parameter constant should suggest
ways to optimize your recursive function. For example:
f(x)=A(x,1) is equivalent to f(x)=2x.
f(x)=A(x,2) is equivalent to f(x)=2^x.
x= 0 1 2 3 4 5 6 7
y=+-----+-----+-----+-----+-----+-----+-----+------+
0 | 1| 2| 4| 5| 6| 7| 8| 9|
1 | 1| 2| 4| 6| 8| 14| 16| 18|
2 | 1| 2| 4| 8| 16| 32| 64| 128|
3 | 1| 2| 4| 16|65536|2^65536 ...
4 | 1| 2| 4|65536| *
5 | 1| 2| 4| *
+-----+-----+-----+
So while something like this:
(defun ackerman (x y)
(cond ((zerop x) 1)
((zerop y) (if (= x 1) 2 (+ x 2)))
(t (ackerman (ackerman (- x 1) y) (- y 1)))))
will work, you could also weed out special cases with something like this:
(defun ackerman (x y)
(cond ((zerop x) 1)
((zerop y) (if (= x 1) 2 (+ x 2)))
((= y 1) (* 2 x))
((= y 2) (expt 2 x))
(t (ackerman (ackerman (- x 1) y) (- y 1)))))
However, as a practical matter, most of the values of Ackerman's
function will either be very easy to compute quickly or they will be
too large to be useful. For example A(4,4)=2^65536 will only fit on a
single standard (8.5"x11") sheet of paper if you use a 4 point (or
smaller) font.
Rick
--
Rick Busdiecker <····@cs.cmu.edu>
``"One of the symptoms of an approaching nervous breakdown is the belief
that one's work is terribly important.'' - Bertrand Russel
If I remember right, the ACKERMAN's FUNCTION is growing faster then every
primitive recursive function and has a definition for every positive arguments.
You can also easy proof the following about this function:
A(1,n) = n + 2
A(2,n) > 2n
A(3,n) > 2^(n+1)
Stefan
----------------------------------------------------------------------
Office: Technische Universitaet Muenchen Phone: +49-89-48095-210
Institut fuer Informatik Fax: +49-89-48095-203
Orleansstr.34 Telex: 3457 tumue d
D-8000 Muenchen 80 Room: 236
Germany
Email: ·······@informatik.tu-muenchen.de
----------------------------------------------------------------------
·······@hamp.hampshire.edu writes:
>While working on a LISP programming excercise, I ran across the following
>recursive function definition:
>ACKERMAN'S FUNCTION
>The function A operates on two arguments m,n
>A(0,n)=n+1
>A(m,0)=A(m-1,1)
>A(m,n)=A(m-1,A(m,n-1))
>Upon programming, I discovered that the definition is deceptive in its
>simplicity. Specifically, does the function has a definition for all
>possible m,n? Is there a more general function to describe this function?
>etc....etc...
A(x,y) is defined if both x and y are greater than or equal to 0. This
is easy to see if we define a partial ordering (x,y) < (x',y') iff
x<x' or (x=x' and y<y'). It is easy to see that there is no infinite
descending chain of pairs in this ordering, and it is also easy to see
that the argument pair to any recursive call is smaller than the left
hand side pair. Thus there is finite recursion, and hence finite time.
As for a "more general function", I assume you mean a closed form
expression, and then the answer is no. If you fix the first argument
to a constant, you can find closed forms for the first few numbers:
A(0,n) = n+1
A(1,n) = n+2
A(2,n) = 2*n+3
A(3,n) = 2^(n+3)-3
A(4,n) = tower2(n+3)-3, where tower2(x) = 2^2^...^2 with x 2's.
A(4,n) thus grows rather fast
A(4,0) = 2^2^2-3 = 13
A(4,1) = 2^2^2^2-3 = 65533
A(4,2) = 2^2^2^2^2-3 = 2^65536-3
...
A(5,n) is of course much worse.
Ackermanns function is the classical example of a recursive function
that is not primitive recursive. All A(k,n) for fixed k are primitive
recursive, but the general function is not.
If you take F(n) = A(n,n) you get an extremely fast growing function.
Though the function itself is not very useful, you can find algorithms
that are not liniear, but are bounded by n*F^(-1)(n), which for all
practical purposes is linear.
Torben Mogensen (·······@diku.dk)
In article <··················@hamp.hampshire.edu>
·······@hamp.hampshire.edu writes:
>
>I am looking for information and references regarding Ackerman's function.
>If anyone can help, send email to ·······@hamp.hampshire.edu
>
I believe the fn was introduced in the following:
Ackermann, W. 1928. Zum Hilbertschen Aufbau der reellen Zahlen.
In Mathematische Annalen, 99, pp. 118-133.
I believe the title would translate something like: Towards a Hilbert
Arrangement (or perhaps reconstruction) of the real numbers.
I have a book somewhere that even mentions some sort of practical utility
for the function (beyond its use in the classroom), but I can't seem to find
it right now.
-Kurt
In article <·················@cmsa.gmr.com> ·······@cmsa.gmr.com writes:
>In article <··················@hamp.hampshire.edu>
>·······@hamp.hampshire.edu writes:
>
>>
>>I am looking for information and references regarding Ackerman's function.
>>If anyone can help, send email to ·······@hamp.hampshire.edu
>>
>I believe the fn was introduced in the following:
>Ackermann, W. 1928. Zum Hilbertschen Aufbau der reellen Zahlen.
>In Mathematische Annalen, 99, pp. 118-133.
>I believe the title would translate something like: Towards a Hilbert
>Arrangement (or perhaps reconstruction) of the real numbers.
>
>I have a book somewhere that even mentions some sort of practical utility
>for the function (beyond its use in the classroom), but I can't seem to find
>it right now.
>-Kurt
>
Ackermann's function makes an appearance in algorithmic complexity
analysis for operations on sets. For the union/find operations
on a representation using compressed trees, the complexity of a sequence
of m operations on n elements, where m >= n and n "makeset" operations,
at most n-1 "union" operations, and the remainder "find" operations,
the amortized complexity is O(m alpha(m,n)), where
alpha(m,n) = min{i >= 1 | A(i, floor(m/n)) > log_2 n}
and A(-,-) is Ackermann's function. Tarjan writes: "[F]or all practical
purposes, alpha(m,n) is a constant not larger than four."
See Tarjan, _Data_Structures_and_Network_Algorithms_, SIAM, 1983.
--
Matthew Saltzman
Clemson University Math Sciences
···@clemson.edu
·······@hamp.hampshire.edu writes:
: While working on a LISP programming excercise, I ran across the following
: recursive function definition:
:
: ACKERMAN'S FUNCTION
: The function A operates on two arguments m,n
: A(0,n)=n+1
: A(m,0)=A(m-1,1)
: A(m,n)=A(m-1,A(m,n-1))
:
: Upon programming, I discovered that the definition is deceptive in its
: simplicity. Specifically, does the function has a definition for all
: possible m,n? Is there a more general function to describe this function?
: etc....etc...
: I am looking for information and references regarding Ackerman's function.
: If anyone can help, send email to ·······@hamp.hampshire.edu
:
: -andrew kriger
In 1988 after perusing Cutland's book on Computability I figured out how to
program least fixed points of recursive functionals directly in C and in
C++, using Cutland's example of the Ackerman operator.
In your example, one would define a functional as follows:
long Ack( long (* f)(long x, long y), long x, long y )
{ if (x == 0)
return y+1;
if (y == 0)
return (*f)(x-1, 1);
return (*f)(x-1, (*f)(x, y-1));
}
Next, define the least fixed point of this operator. A fixed point of the
Ack() functional is a function
long fixpoint( long a, long b )
that satisfies the functional equation
fixpoint(x, y) = Ack(fixpoint, x, y) for all x, y.
There is essentially one way to define this in C (or C++):
long fixpoint(long a, long b)
{ return Ack(fixpoint, a, b);
}
All that I have done is postpone the recursion with these definitions,
but they do work, and you can see them work in conventional programming
languages (correct me if I'm wrong, but I have gotten the impression that
least fixed point approaches to recursion are of more theoretical than
practical interest. In this example you can see that they are easy
enough to set up).
One can go a little further by defining a fixed point operator:
long fix( long (*F)(long (*f)(long a, long b), long a, long b), long x, long y)
{
return (*F)( (long (*)(long a, long b)) fix, x, y);
}
which associates to a functional of type
long F(long (*)(long a, long b), long a, long b)
its least fixed point.
Please excuse the type-casting. This looks relatively trivial to me,
however, since I did copyright this in 1988 I will include my notice
here for good measure: (c) 1988, 1989, 1992 by Florian Lengyel.
Also, I have this fantasy for which I would be grateful to any of you
if you could disabuse me of it, namely, that this could be useful in
some way. I was hoping with these definitions (and others like them)
to get away with a kind of computational murder: I would love to
avoid programming (except implicitly, using these functional equations)
by perhaps writing down a functional or a series of functionals
and then compute their least fixed point
fix = Functional(fix, x_0, \ldots ,x_{n-1})
which would construct my program as a solution to a functional
equation, from which I could conclude that my program met all of its
implicitly defined constraints. I suppose I won't admit to myself that
I really require another form of the Recursion Theorem in order to
pull that kind of stunt off, but because I have not met a soul anywhere
who was in a position to tell me this, or who had seen a program like
this, I have at last decided to subject USENET to it.
Over and out,
--
········@DORSAI.COM
·······@NEOTERIC.COM
From: Bryan Carpenter
Subject: Re: Ackerman's function
Date:
Message-ID: <13242@ecs.soton.ac.uk>
In <······················@dorsai.com> ········@dorsai.com (Florian Lengyel) writes:
>...
>In 1988 after perusing Cutland's book on Computability I figured out how to
>program least fixed points of recursive functionals directly in C and in
>C++, using Cutland's example of the Ackerman operator.
>...
>One can go a little further by defining a fixed point operator:
>long fix( long (*F)(long (*f)(long a, long b), long a, long b), long x, long y)
>{
> return (*F)( (long (*)(long a, long b)) fix, x, y);
>}
>which associates to a functional of type
> long F(long (*)(long a, long b), long a, long b)
>its least fixed point.
>...
>Also, I have this fantasy for which I would be grateful to any of you
>if you could disabuse me of it, namely, that this could be useful in
>some way. I was hoping with these definitions (and others like them)
>to get away with a kind of computational murder: I would love to
>avoid programming (except implicitly, using these functional equations)
>by perhaps writing down a functional or a series of functionals
>and then compute their least fixed point
> fix = Functional(fix, x_0, \ldots ,x_{n-1})
>which would construct my program as a solution to a functional
>equation, from which I could conclude that my program met all of its
>implicitly defined constraints. I suppose I won't admit to myself that
>I really require another form of the Recursion Theorem in order to
>pull that kind of stunt off, but because I have not met a soul anywhere
>who was in a position to tell me this, or who had seen a program like
>this, I have at last decided to subject USENET to it.
It's interesting that you can do this sort of thing in C. But
what you're describing sounds not-a-million-miles from functional programming,
and it's much easier to express these sorts of things
in a proper functional language. If the language doesn't
have the fixpoint operator as a primitive anyway, you can
define it as
fix :: ((a -> b) -> (a -> b)) -> (a -> b)
fix f = f (fix f)
This will return the least fixpoint of any function from a to b
(it's a polymorphic function). Your Ack function becomes
ack :: ((Integer, Integer) -> Integer) -> ((Integer, Integer) -> Integer)
ack f (x, y) | x == 0 = y + 1
| y == 0 = f (x - 1, 1)
| otherwise = f (x - 1, f (x, y - 1))
and you evaluate the Ackermann function at (2, 3) by
(fix ack) (2, 3)
This syntax is Haskell, but it will be very similar in any functional
language.
>Over and out,
>--
>········@DORSAI.COM
>·······@NEOTERIC.COM
Bryan