Ackermann

Problem

Let f be a function defined by the following:

  1. f(0, n) = n + 1
  2. f(m+1, 0) = f(m, 1)
  3. f(m+1, n+1) = f(m, f(m+1, n))

being m and n natural numbers.

What is the value of f(4, 1981)?

Solution

Let’s start with the values of f(1, n):

f(1, n) = f(0, f(1, n-1)) (Eq. 3)

f(1, n) = f(1, n-1) + 1 (Eq. 1)

Continuing the process we get

f(1, n) = f(1, n-n) + n = f(1, 0) + n

f(1, n) = f(0, 1) + n (Eq. 2)

f(1, n) = 1 + 1 + n = n + 2 (Eq. 1)

ending with the expression

f(1, n) = n + 2.

Now we can try to get the values of f(2, n):

f(2, n) = f(1, f(2, n - 1)) = f(2, n - 1) + 2 (Eq. 3).

Repeating the process we end with

f(2, n) = f(2, n - n) + 2n = f(2, 0) + 2n

f(2, n) = f(1, 1) + 2n = 1 + 2 + 2n = 2n + 3

f(2, n) = 2n + 3.

Using this result to get f(3, n):

f(3, n) = f(2, f(3, n - 1)) = 2 f(3, n-1) + 3.

Iterating this process we reach

f(3, n) = 2 f(2, f(3, n - 2)) + 3 = 2 (2 f(3, n-2) + 3) + 3 = 2^2 f(3, n-2) + 3(2^1 + 2^0)

f(3, n) = 2^2(2 f(3, n-3) + 3) + 3(2^1 + 2^0) = 2^3 f(3, n-3) + 3(2^2 + 2^1 + 2^0)

f(3, n) = 2^n f(3, 0) + 3(2^n - 1)

f(3, n) = 2^n f(2, 1) + 3(2^n - 1) (Eq. 2)

f(3, n) = 2^n 5 + 3(2^n - 1) = 8 2^n - 3 = 2^{n+3} - 3

f(3, n) = 2^{n+3} - 3.

f(4, n) is finally in sight 😀 Replacing:

f(4, n) = f(3, f(4, n - 1)) (Eq. 3)

f(4, n) = 2^{f(4, n - 1)+3} - 3 = 2^3 2^{f(4, n - 1)} - 3.

Making some additional iterations to get the pattern:

f(4, n) = 2^3 2^{f(3, f(4, n - 2))} - 3 (Eq. 3)

\displaystyle f(4, n) = 2^3 2^{2^{f(4, n - 2)+3} - 3} - 3

\displaystyle f(4, n) = 2^3 2^{-3} 2^{2^3 2^{f(4, n - 2)}} - 3 = 2^{2^3 2^{f(4, n - 2)}} - 3

\displaystyle f(4, n) = 2^{2^3 2^{2^3 2^{f(4, n - 3)} - 3}} - 3 (Eq. 3)

\displaystyle f(4, n)  = 2^{2^{2^3 2^{f(4, n - 3)}}} - 3

Now the progression is clear: each iteration adds one 2 to the exponential tower and the 2^3 term moves with f. Let’s define a function to encapsulate the tower exponential:

\mathrm{tow}(0, k) = k

\mathrm{tow}(n+1, k) = 2^{\mathrm{tow}(n, k)}

(\mathrm{tow}(n, 1) corresponds to a tower of n 2s).

Then we can iterate until reaching

f(4, n) = \mathrm{tow}\left(n-1, 2^3 2^{f(4, n - n)}\right) - 3 = \mathrm{tow}\left(n-1, 2^{3  + f(4, 0)}\right) - 3

f(4, n) = \mathrm{tow}\left(n, 3  + f(4, 0)\right) - 3.

Getting f(4, 0):

f(4, 0) = f(3, 1) = 2^{1+3} - 3 = 13

Replacing:

f(4, n) = \mathrm{tow}\left(n, 16\right) - 3 = \mathrm{tow}\left(n, 2^{2^2}\right) - 3 = \mathrm{tow}\left(n + 3, 1\right) - 3

Final result

Then the asked for value is f(4, 1981) = \mathrm{tow}\left(1984, 1\right) - 3 in our notation.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s