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