The Miranda Programming Language

Ackermann's Function in Miranda

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

Description

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.

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