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 ***************************************************}