Re: [FWP] Ackerman

["Abigail" <abigail@foad.org>]

On Wed, Jun 27, 2001 at 11:46:03PM +0100, csaba.raduly@sophos.com wrote:
> 
> 
> Abigail wrote:
> > On Wed, Jun 27, 2001 at 10:47:37AM +0100, csaba.raduly@sophos.com wrote:
> > > Do you think your computer has too much memory ? Give it a workout!
> [snip my script using the following formula]
> > > sub Acker
> > > {
> > >    my ( $m, $n ) = @_;
> > >    if( $m==0 ){
> > >       return $n+1;
> > >    }
> > >    if( $n==0 ){
> > >       return Acker( $m-1, 0 );
>                               ^
> This should be 1, not 0 ------^
> 
> > >    }
> > >    return Acker( $m-1, Acker($m,$n-1) );
> > > }
> > >
> > > This script computes the Ackerman function, The Most Fiendishly
> Recursive
> > > Function Known To Man (tm).
> >
> > Eh, no, it doesn't. It starts off with:
> >
> >         A( 1, 0 ) = 2
> >                         1,1
> >         A( 1, 1 ) = 3
> >                         1,2
> >         A( 1, 2 ) = 4
> >                         1,3
> >         A( 1, 3 ) = 5
> >                         1,4
> >         A( 1, 4 ) = 6
> >                         1,5
> >         A( 1, 5 ) = 7
> >                         1,6
> >         A( 1, 6 ) = 8
> >                         1,7
> >         A( 1, 7 ) = 9
> >                         1,8
> >
> > which are numbers that are way too low.  The rest of the numbers are
> > way too low too.
> 
> At least the results above *are* correct. Purely by accident :-(
> 
> A(0,n) = n+1           =  n + 1
> A(1,n) = 2 + (n+3) - 3 =  n + 2
> A(2,n) = 2 * (n+3) - 3 = 2n + 3
> A(3,n) = 2 **(n+3) - 3
> 
> See for example http://public.logica.com/~stepneys/cyc/a/ackermnn.htm
> 
> > Acker (3, 5) for instance is a number with almost
> > 20k digits.
> 
> Nope, Acker(3,5) = 2**(5+3) - 3 = 253
> Acker(3,5) = A( 2, A(3,4) ) = A( 2, 125 ) = A( 1, A(2,124) )
> 
> It's A( 4,2 ) which has 19729 digits.


I've seen slight variations in definitions of the Ackermann function,
but they all differ in whether to start counting at 0 or 1, and in
which order to give the arguments.

I've never seen a definition of the Ackermann function where the values
aren't powers of 2 (except for the first column where they are multitudes
of 2).

The definition found in [2] gives the same values as in [1], except
the table is slightly shifted. 


Your values seem to match mine, if you would add 3 to them, and shift
your table a bit.


[2] Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest:
   "Introduction to Algorithms". Cambridge: MIT Press, 1990.
    ISBN 0-262-03141-8.



Abigail

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe