How to resolve the algorithm Ackermann function step by step in the Prolog programming language

Published on 12 May 2024 09:40 PM
#Prolog

How to resolve the algorithm Ackermann function step by step in the Prolog programming language

Table of Contents

Problem Statement

The Ackermann function is a classic example of a recursive function, notable especially because it is not a primitive recursive function. It grows very quickly in value, as does the size of its call tree.

The Ackermann function is usually defined as follows:

Its arguments are never negative and it always terminates.

Write a function which returns the value of

A ( m , n )

{\displaystyle A(m,n)}

. Arbitrary precision is preferred (since the function grows so quickly), but not required.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Ackermann function step by step in the Prolog programming language

Source code in the prolog programming language

:- table ack/3. % memoization reduces the execution time of ack(4,1,X) from several
                % minutes to about one second on a typical desktop computer.
ack(0, N, Ans) :- Ans is N+1.
ack(M, 0, Ans) :- M>0, X is M-1, ack(X, 1, Ans).
ack(M, N, Ans) :- M>0, N>0, X is M-1, Y is N-1, ack(M, Y, Ans2), ack(X, Ans2, Ans).

ack(0,N,s(N)).
ack(s(M),0,P):- ack(M,s(0),P).
ack(s(M),s(N),P):- ack(s(M),N,S), ack(M,S,P).

% Peano's first axiom in Prolog is that s(0) AND s(s(N)):- s(N)
% Thanks to this we don't need explicit N > 0 checks.
% Nor explicit arithmetic operations like X is M-1.
% Recursion and unification naturally decrement s(N) to N.
% But: Prolog clauses are relations and cannot be replaced by their result, like functions.
% Because of this we do need an extra argument to hold the output of the function.
% And we also need an additional call to the function in the last clause.

% Example input/output:
% ?- ack(s(0),s(s(0)),P).
% P = s(s(s(s(0)))) ;
% false.

You may also check:How to resolve the algorithm Abundant, deficient and perfect number classifications step by step in the D programming language
You may also check:How to resolve the algorithm Guess the number step by step in the Forth programming language
You may also check:How to resolve the algorithm Check that file exists step by step in the VBScript programming language
You may also check:How to resolve the algorithm Aliquot sequence classifications step by step in the Julia programming language
You may also check:How to resolve the algorithm MD4 step by step in the JavaScript programming language