# Ackermann function (Prolog)

### From LiteratePrograms

The **Ackermann function** or **Ackermann-Péter function** is defined recursively for non-negative integers *m* and *n* as follows:

- 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}"/>

In the theory of computation, the Ackermann function is a simple example of a recursive function that is not primitively recursive. Note that this function grows very quickly -- even `A(4, 3)`

cannot be feasibly computed on ordinary computers.

This page explains how to implement the **Ackermann function** in Prolog. In Prolog, functions are defined as relations while both the arguments and the result are given to the relation as parameters. In this article, `ackermann(M, N, A)`

denotes that '`A`

is the value of .'

## Source code

The source code is composed of three cases explained above.

1. if m = 0

<<ackermann.pl>>=ackermann(0, N, A) :- A is N + 1.

Note that the `is`

operator assigns the arithmetic operation to the variable.

2. if m > 0 and n = 0

<<ackermann.pl>>=ackermann(M, 0, A) :- M > 0, M1 is M - 1, ackermann(M1, 1, A).

3. if m > 0 and n > 0

<<ackermann.pl>>=ackermann(M, N, A) :- M > 0, N > 0, M1 is M - 1, N1 is N - 1, ackermann(M, N1, Temp), ackermann(M1, Temp, A).

This case is a little tricky. As logic programming languages do not support functional composition, we have to employ a temporary variable `Temp`

for .

## Tricky version

In this version we use the `!`

(the cut operator) to avoid unnecessary backtracking. Also
the try_asserta/1 predicate is an effort to save intermediate results thus using them when needed,
some useless comparisons checks are removed too.

```
tricky_ackermann.pl
:- dynamic acr/3.
try_asserta(F) :- % if we already have the result do nothing
F,
!.
try_asserta(F) :- % if we do not have the result store it
!,
asserta(F).
ackermann(M, N, A) :- % use precomputed result if that exists
acr(M, N, A),
!.
ackermann(0, N, A) :- % special case
!,
A is N + 1,
try_asserta(acr(0, N, A)).
ackermann(M, 0, A) :- % special case
!,
M1 is M - 1,
ackermann(M1, 1, A),
try_asserta(acr(M, 0, A)),
try_asserta(acr(M1, 1, A)).
ackermann(M, N, A) :- % main recursions
!,
M1 is M - 1,
N1 is N - 1,
ackermann(M, N1, Temp),
try_asserta(acr(M, N1, Temp)),
ackermann(M1, Temp, A),
try_asserta(acr(M, N, A)),
try_asserta(acr(M1, Temp, A)).
```

## Execution result

This section contains a number of execution results of the Ackermann function implementation in Prolog.

crypto@crypto ~/gcd_prolog $ prolog Welcome to SWI-Prolog (Multi-threaded, Version 5.2.6) Copyright (c) 1990-2003 University of Amsterdam. SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- ['ackermann.pl']. % ackermann.pl compiled 0.00 sec, 1,112 bytes Yes ?- ackermann(0, 0, A). A = 1 Yes ?- ackermann(1, 6, A). A = 8 Yes ?- ackermann(2, 3, A). A = 9 Yes ?- ackermann(3, 3, A). A = 61 Yes ?- ackermann(4, 3, A). ERROR: Out of local stack ?-