The Miranda Programming Language

Ackermann's Function in Miranda

Click below to go directly to a specific section:
Description | Source CodeProgram Notes


The Ackermann function is the simplest example of a well-defined total function which is computable but not primitive recursive.  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))

This example implements Ackermann's function in Miranda.

Source Code

ack 0 n = n+1
ack (m+1) 0 = ack m 1
ack (m+1) (n+1) = ack m(ack (m+1) n)

Program Notes

Due to the unavailability of a Miranda compiler, an executable program is not available. 
[Prev] [Home]

Last modified: 04:20 PM on 12/16/1997