Conference turris::languages

    I have a data structures book ("Fundamentals of Data Structures"
    by Horowitz and Sahni, 1976) with two different definitions of
    Ackermann's function:
    
    1)	A(m,n) =	n+1			, if m = 0
    			A(m-1, 1)		, if n = 0
    			A(m-1, A(m, n-1))	, otherwise
    
    
    2)	A(p,q) =	2q			, if p = 0
    			0			, q = 0 and p >= 1
    			2			, p >= 1 and q = 1
    			A(p-1, A(p, q-1))	, p >= 1 and q >= 2
    
    
    I believe (1) is the actual definitions of Ackermann's function;
    (2) appears to be a modification designed to simplify the ensuing
    discussion.
    
    	- Jerry

    One of my most bitter memories of CS classes (and there are few)
    was near the beginning of my course on "Programming Languages"
    (mainly LISP and SNOBOL) where the instructor described Ackermann's
    function to us (not by name) and gave as a homework assignment to
    come up with an iterative algorithm for it.  I beat my brains against
    the wall for days, and felt like shooting the instructor when he
    told us that it took some fifty years (or more) for someone to
    finally come up with an iterative solution.  He must have thought it 
    was funny.
    					Steve

    I think the reason this was given to the particular class while
    studying recursion, was to show that recursive algorithms, some-
    times aren't the best.  The class being made up of summer sophmores,
    didn't realize that A(4,2) was impossible to solve on the 11/70
    they were using.  (Berkeley 2.9 UNIX and Pascal).  I don't think
    they were ever told either.
    
    re: .1  Thanks for the info.
    
    					Alan
    

    As I recall, Ackermann's function was devised to prove that all
    iterative algorithms could be written recursively, but that the
    converse was not true.  As I said, it took a LONG time for someone
    to come up with a clever (and simple, once you saw it) way to
    compute Ackermann's iteratively.
    				Steve

Re .1:

FWIW, while I've seen several definitions, your #1 is the one I am used
to dealing with.

Re .2:

I once discovered out that for each value of m, you get a relatively simple
closed form expression in n.  But for each increase in m, a higher-order
arithmetic operator is used (addition, multiplication, exponentiation,
...).  Since the only way I know to describe the higher-order operators
is recursive, that begs the question.

Re .3:

I don't remember the magnitude of A(4,2), but if it didn't require multiple
precision arithmetic, the problem was quite solvable on an 11/70.  Most
of the recusive calls are for values that have already been computed.
If you simply cache the values of A(m,n) on the fly, and look them up
before attempting to compute them, it greatly speeds up the algorithm,
at least in the small region I have experience with.


A professor at my college unknowingly assigned something that was not
representable in 36 bits (A(4,3)?) in an introduction to assembly language
course.  Since overflow from addition was not detected by default, no one
could figure out why they were getting partial results that were negative
when the numbers wrapped around.  (Yes, it was during the section on
recursion that the assignment was made).
				/AHM

    So, what is the iterative algorithm?  
    
    I remember writing Ackermann's function in UNIX shell once.  Talk
    about slow. 
    
                                        August G. Reinig

    Sorry, I don't recall the iterative solution.  It was thirteen years
    ago!
    			Steve

    After looking at some results of the recursive version, I've
    notice that:
    
    	Ackermann(3,n) = ( 2 ** ( n + 3 )) - 3
    
    I'm running Ackermann(4,1) on my workstation and the local
    8650 now.  If I remember correctly it is 65533 ( +/- a
    couple).  It looks like Ackermann(4,2) really will in the
    neighborhood of:
    
    	2 ** 65534 - 3
    
    My recursive version is braindamaged, because I didn't put
    in any value cacheing.  I'll probably add a table of inter-
    mediate values to the next version, so it won't have to
    recalculate each one.

    					Alan

    Below is the "smart" version of my program to calculate a value for
    Ackermann's function.  It doesn't do any bounds checking for "known"
    maximium values (Ackermann(3,big)).
    
    It was written in about two hours and compiles and runs on Ultrix
    and VMS.  It hasn't had any lint dusted off yet.  The next version
    will have comments.  It is also reasonably fast.  My Ultrix work-
    station found Ackermann(4,1) in 12.8 seconds (9.3 user, 3.5 system).
    The selection of 65536 for N was arbitrary.
    
    					Alan
    
- - - - - - - - - - - - - - - - CUT HERE - - - - - - - - - - - - - - - - - - - -
/*
 *	Author:  Alan Rollow, EIS/CXO, Digital Equipment Corp.
 *	File:	 Ackermann.c
 *	Date:	 10/8/86
 *	Version: 1.2
 *
 *	Ackermann.c - Recursive version of Ackermann's function.  After
 *	Ackermann(4, 0) it really gets nasty.
 */
#ifndef	lint
static	char	SccsId[] = "@(#)Ackermann.c	1.2 10/8/86" ;
#endif

#include <stdio.h>
#include <errno.h>
#include <signal.h>

int	depth = 0, lookup = 0 ;

#define	M	4
#define	N	65536

/*
 *	Tacky humor has no place in serious programing...  But
 *	whoever said that was serious...
 */
struct	bill_the_cat {
	int	ack_value ;
	int	ack_flag ;
} table[M][N] ;

main(argc, argv)
int	argc ;
char	*argv[] ;
{
	register m, n ;
	int	 catch() ;

	if( argc != 3 ) {
		printf("usage: Ackermann m n\n") ;
		exit(EINVAL);
	}

	m = atoi(argv[1]) ;
	n = atoi(argv[2]) ;

	(void)signal(SIGINT, catch) ;
	(void)signal(SIGTERM, catch) ;

	printf("Ackermann(%d,%d) = %d\n", m, n, Ackermann(m, n));
	printf("Depth: %d, Lookup: %d\n", depth, lookup);
}

Ackermann(m, n)
register m, n ;
{
	register value ;

	if( m < M && n < N && table[m][n].ack_flag ) {
		lookup++ ;
		return table[m][n].ack_value ;
	}

	depth++ ;

	if( m == 0 )
		value = n + 1 ;
	else if( n == 0 )
		value = Ackermann(m - 1, 1) ;
	else
		value = Ackermann(m - 1, Ackermann(m, n - 1)) ;

	if( m < M && n < N ) {
		table[m][n].ack_value = value ;
		table[m][n].ack_flag = 1 ;
	}

	return value ;
}

catch()
{
	printf("\nDepth of \"recursion\" when stopped: %d\n", depth) ;
	printf("Number of lookups: %d\n", lookup);
	fflush(stdout) ;
	exit(0) ;
}
    

You can halve your space usage by using a zero cache entry as the flag that
no number is stored there yet.  This also results in fewer instructions to
access the entries of table[][], although changing table to a struct
of two arrays instead of an array of two-member structs would probably
accomplish the same thing.

I was going to claim it makes a significant speedup in A(4,1), but I only
tried a half a dozen times, using my cursor blink as a timer, and the times
for the same version of the program on the same data seem to have a lot of
deviation.  I'm on an 8800, maybe it depends on which processor I get
scheduled on.

Unfortunately, Vax C doesn't CSE the two accesses to table[][] in the
revised program, probably because it doesn't realize that a test against
zero could fetch the value of the table into an AC.  What's worse, it
doesn't CSE the index computations, either.  However, with the large cache,
and highly recursive nature of the algorithm, I assume the program spends
most of its time waiting for memory, rather than doing address arithmetic.
				/AHM

    re: 10
    
    Since I know that a value for Ackermann(m,n) will never be zero
    (for non-negitive m and n), then using a zero value as a flag
    seems very reasonable.  I'll add this to the next version and
    provide a pointer to the source in a future note.
    
    I spent a couple of hours last night looking for an iterative
    solution and only succeeded in realizing that I'm not sure that
    Ackermann(4,2) is ( 2 ** 65533 - 3 ).  Looking at the other
    values of Ackermann(4,n) that I can find, it might be ( 2 ** 65536
    - 3 ).  Either one I can find the value for using the Ultrix
    libmp functions.  If anybody knows which of those is correct
    please let me know.
   
    The problem has me interested again, for the simple reasons that
    the problem is there (like Mt. Everest) it is there, I CAN find
    the solution, but I'm not sure if it is right.
     
    Other interesting Ackermann's:
    
    	Ackermann(5,0) = 65533
    	Ackermann(3,n) = ( 2 ** ( m + n )) - 3
    	Ackermann(2,n) = ( 2 * ( m + n + 1 )) - 3
    
    					Alan
    
   

Re .11:

It is possible to derive a closed-form expression for A(4,n) from your
closed form expression of A(3,n) (although it may require a new arithmetic
operator to express it properly).

Note that you haven't removed all the m's from your closed form expressions
for A(2,n) and A(3,n).
				/AHM

	Something about the proverbial snake comes to mind...

	The closed forms:

		Ackermann(0,n) = n + 1 (the definition)
		Ackermann(1,n) = 2 + ( n + 3 ) - 3 = n + 2
		Ackermann(2,n) = 2 * ( n + 3 ) - 3 = 2n + 3
		Ackermann(3,n) = 2 ** ( n + 3 ) - 3

	Ackermann(4,n) I still haven't gotten.  I know that for
	(4,0) it is 13 and for (4,1) it is 65533.  I believe
	(from previous exposure to the problem) that (4,2) is
	2 ** 65534 - 3, but I can't prove it (1).  Possible
	solutions are:

		2 *** ( n + 3 ) - 3   (2)
		f(n) - 3
		2 ** g(n) - 3

	If anybody knows the iterative solution, let me know.  I'm
	better at finding the value, then the algorithm.

	I'm taking a couple of days vacation to go watch Oklahoma
	beat saxeT in Dallas, but will look in again Monday night.

	The source to the current version of my program will be
	in:
		COOKIE::DISK$NEWTON_2:[ROLLOW.SRC.ACKERMANN]ACKERMANN.C
	or:
		NABETH::"/usr/users/alan/src/Ackermann/Ackermann.c"
		(I think DECNET/Ultrix understands ~, so you might
		 be able to use ~alan for less typeing.)

				* * *

	Footnotes:

	1.  I had previously written this as 2 ** 65533 - 3, but
	2 ** 65534 - 3 was the value a found a couple of years ago
	so it is the one I'll go with.  It was induced from a sum-
	mation worked out by the person who had originally had the
	problem as an assignment.

	2.  The other Alan's "new" operator.
    

    Another version of Ackerman(4,0) and (4,1)
    
    	Ackermann(4,0) = ( Summation of 2 ** n for n = 1 to 3 ) - 1
    	Ackermann(4,1) = ( Summation of 2 ** n for n = 1 to 15 ) - 1
    
    My suggestion for Ackermann(4,2) was induced from:
    
    	( Summation of 2 ** n for n = 1 to 65533 ) - 1

    Well gotta leave before the phone line noise, blows me up...
    
    					Alan
    

If anyone is interested, I have the answer in a file that I can mail you.
Its 19729 digits and starts with 20035299... and ends with ...19156733.
To come back to the original subject of this notesfile: it was done in a
language that wasn't mentioned before. It's called TRAC, invented in the
early sixties by Calvin Mooers. Features: infinite length arithmetic,
recursion, powerful patternmatching (like Snobol), code=data (like Lisp),
no difference in deproceduring, evalutation, control, declaration and so on.
I have an implementation that runs under VMS, Ultrix and Venix.
Using the closed formula's for m=1,2,3, it looks as follows in TRAC:
 
:(ds,ackerman,(:(gr,1,#1,(:(ad,#2,1)),(:(eq,#1,1,(:(ad,#2,2)),(:(eq,#1,2,
(:(ad,#2,:(ad,#2,3))),(:(eq,#1,3,(:(su,:(pow,2,:(ad,#2,3)),3)),
(:(gr,#2,0,(:(ackerman,:(su,#1,1),:(ackerman,#1,:(su,#2,1)))),
(:(ackerman,:(su,#1,1),1))))))))))))):(ss,ackerman,#1,#2)

								Hans.

    Re .4:

    > As I recall, Ackermann's function was devised to prove that all
    > iterative algorithms could be written recursively, but that the
    > converse was not true.

    Ackermann's function is an example of a function that cannot be
    computed with bounded loops.  A bounded loop is one for which the
    number of iterations can be computed before the loop begins (like "for"
    loops with a variable going from 1 to n).  By contrast, unbounded loops
    iterate until some condition is reached (like "while" loops with a
    general Boolean expression).  No number of nested bounded loops can
    compute Ackermann's function.

    This is not about recursion versus iteration.  Every recursive function
    can be computed iteratively, with unbounded loops.

    > As I said, it took a LONG time for someone to come up with a clever
    > (and simple, once you saw it) way to compute Ackermann's iteratively.

    I don't think this was reported correctly.  There are standard
    techniques for converting recursive functions to iterative functions. 
    The demonstrations used in theory classes aren't necessarily efficient,
    but they could be made efficient without too much trouble.  Here is an
    example.  It uses arbitrarily large integers to store a stack.  We push
    a number on the stack by raising 2 to the power of the stack and
    multiplying by an odd number.  We pop a number from the stack by
    finding the largest power of 2 that divides the stack -- the quotient
    is the pushed odd number, and the power is the previous stack.  Since
    we do not always want to push an odd number, we use 2*k+1 as the odd
    multiplier when we want to push k.
    
    Given this stack, we simply make a loop that computes A(m,n).  When m
    and n are not zero, this is defined as A(m-1,A(m,n-1)), which we
    compute by pushing m-1 onto the stack and then computing A(m,n-1). 
    When the computation of A(m,n-1) is done, we pop the stack -- putting
    the computed value into n and restoring m by popping it from the stack.

    Compute A(m,n):

    stack=1;
    while (stack > 0) {
    	if (m==0) {
    		/* We are done computing something.  The answer is n+1,
    		   which we put in n, after popping the stack. */
    		t = largest power of 2 that divides stack;
    		m = (stack/t-1)/2;
    		stack = log base 2 of t;
    		n = n+1;
    	}
        else if (n==0) {
    		/* A(m,0) is just A(m-1,1). */
    		m = m-1;
    		n = 1;
    	}
    	else {
    		/* A(m,n) is A(m-1,A(m,n-1)).  Push m-1 and then set
    		   m and n to compute A(m,n-1). */
    		stack = (2 to the power of stack) * (2*m-1);
    		n = n-1;
    	}
    }
    return n;


    				-- edp


Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

    Here's a short loop to compute Ackermann's function, in C with very
    long integers:
    
    	s = t = m+2;
        while (s >= t)
            if (!m--)     m = s%t, s /= t, n++;
            else if (n++) s = s*t+m++, n -= 2;
    
    When the loop exits, n is the value of A(m,n).
    
    
    				-- edp