Ackerman.PAS Program Listing

{ Start of file Ackerman.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 Ackerman; { Tries to compute the Ackermann function A = A(x, y) }

uses Crt; { Turbo Pascal interface }

const                 
  Name    = 'Ackerman - 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))
}

var
  x, y, z,
  Calls    : 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:= ' ';
end; { Init }

{--------------------------------------}
function A(x, y : LongInt) : LongInt; { Ackermann function }
begin
  Inc( Calls);
  if KeyPressed then begin
    Ch:= ReadKey;
    if (Ch = Char(27))  then Halt;
  end;
  if      (x = 0) then  A:= y+1
  else if (y = 0) then  A:= A(x-1, 1)
  else                  A:= A(x-1, A(x, y-1));
end; { A }

{--------------------------------------}
begin { Main program, Ackerman }
  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. { Ackerman }

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