Acker2.PAS Program Listing

{ Start of file Acker2.PAS *************************************************}

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,R-,S+,V+,X-} { Pascal defaults }
{$M 16384,0,655360}

{$M 65520, 0, 655360} { 16384, 0, 655360 are defaults; $M 65520 max stack }

program Acker2; { Tries to compute the Ackermann function A = A(x, y) }

uses Crt; { Turbo Pascal interface }

const                 
  Name    = 'Acker2 - Tries to compute the Ackermann function A = A(x, y)';
  Version = 'Version 1.00, last revised: 91/11/02, 0600 hours';
  Author  = 'Copyright (c) 1991 by author: Harry J Smith,';
  Address = '19628 Via Monte Dr., Saratoga CA 95070.  All rights reserved.';

{***************************************************************************}

{ Developed in TURBO Pascal 6.0 }

{ The Ackermann function is the simplest example of a well-defined total
  function which is computable but not primitive recursive.  See the
  article "A function to end all functions" by Günter Dotzel, Algorithm 2.4,
  Oct 1991, Pg 16.  The function f(x) = A(x, x) grows much faster than 
  polynomials or exponentials.  The definition is:

	1. If x = 0 then  A(x, y) = y + 1
	2. If y = 0 then  A(x, y) = A(x-1, 1)
	3. Otherwise,     A(x, y) = A(x-1, A(x, y-1))
}

const
  MaxX = 1;
  MaxY = 8000;

var
  x, y, z,
  Calls    : LongInt;
  ATab     : array[0..MaxX, 0..MaxY] of LongInt;
  Ch       : Char;

{--------------------------------------}
procedure Init; { Initialize program }
begin
  TextBackground( Blue);
  TextColor( Yellow);
  ClrScr;
  WriteLn;
  WriteLn;
  WriteLn( Name);
  WriteLn( Version);
  WriteLn( Author);
  WriteLn( Address);
  WriteLn;
  WriteLn('The definition is:');
  WriteLn;
  WriteLn('   1. If x = 0 then  A(x, y) = y + 1');
  WriteLn('   2. If y = 0 then  A(x, y) = A(x-1, 1)');
  WriteLn('   3. Otherwise,     A(x, y) = A(x-1, A(x, y-1))');
  WriteLn;
  WriteLn( 'To exit, enter x < 0 or y < 0');
  WriteLn( '  or press ESC during a calculation');
  WriteLn;
  Ch:= ' ';
  for x:= 0 to MaxX do
    for y:= 0 to MaxY do
      ATab[x, y]:= 0;
end; { Init }

{--------------------------------------}
function A(x, y : LongInt) : LongInt; { Ackermann function }
var T : LongInt;
begin
  Inc( Calls);
  if KeyPressed then begin
    Ch:= ReadKey;
    if (Ch = Char(27))  then Halt;
  end;
  if (x <= MaxX) and (y <= MaxY) then
    if (ATab[x, y] <> 0) then begin
      A:= ATab[x, y];  Exit;
    end;
  if      (x = 0) then  T:= y+1
  else if (y = 0) then  T:= A(x-1, 1)
  else                  T:= A(x-1, A(x, y-1));
  A:= T;
  if (x <= MaxX) and (y <= MaxY) then
    ATab[x, y]:= T;
end; { A }

{--------------------------------------}
begin { Main program, Acker2 }
  Init; { Initialize program }
  repeat
    Write('?, x = ');  ReadLn( x);
    Write('?, y = ');  ReadLn( y);
    if (x >= 0) and (y >= 0) then begin
      Calls:= 0;
      z:= A(x, y);
      WriteLn('A(', x, ', ', y, ') = ', z, '  in ', Calls, ' Calls');
    end;
    WriteLn;
  until (x < 0) or (y < 0);
end. { Acker2 }

{ End of file Acker2.PAS ***************************************************}