Question

Find these values of Ackermann’s function.

1. A (1,0)
2. B (0,1)
3. C (1,1)
4. D (2,2)

Short answer

1. The value of A (1,0) is 2.
2. The value of B (0,1) is 2.
3. The value of C (1,1) is 3.
4. The value of D (2,2) is 7.

Step-by-step solution

Step 1:Introduction

The Ackermann function is defined as the simplest example of a well-defined total function that is computable but not primitive recursive.

(a) Find  

There are several different variants of this function. All are calledAckermann’s functions and have similar properties even though their values do not always agree. One common version, the two-argument Ackermann-Peter function, is defined as follows

For nonnegative integers m and n :

$A(m,n)=\left\{\begin{array}{l}n+1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}m=0\\ A(m-1,1)\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}m>0\text{and}n=0\mid \\ A(m-1,A(m,n-1\left)\right)\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}m>0\text{and}n>0\end{array}\right.$

Its value grows rapidly, even for small inputs.

A (1,0) = A (1 - 1,1)

= A (0,1)

By the above definition of Ackermann’s function,

This implies;

A (0,1) = 1+1

= 2

Hence, the value is 2.

:( b) Find  

There are several different variants of this function. All are calledAckermann’s functions and have similar properties even though their values do not always agree. One common version, the two-argument Ackermann-Peter function, is defined as follows

For nonnegative integers and :

$\mathrm{A}(\mathrm{m},\mathrm{n})=\left\{\begin{array}{l}\mathrm{n}+1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}=0\\ \mathrm{A}(\mathrm{m}-1,1)\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}>0\text{and}\mathrm{n}=0\\ \mathrm{A}(\mathrm{m}-1,\mathrm{A}(\mathrm{m},\mathrm{n}-1\left)\right)\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}>0\text{and}\mathrm{n}>0\end{array}\right.$

Its value grows rapidly, even for small inputs.

A (0,1) = A (1- , 1,1)

By the above definition of Ackermann’s function,

This implies;

A (0,1) = 1+1

= 2

Hence, the value is 2.

(c) Find  

There are several different variants of this function. All are calledAckermann’s functions and have similar properties even though their values do not always agree. One common version, the two-argument Ackermann-Peter function, is defined as follows

For nonnegative integers m and n:

$\mathrm{A}(\mathrm{m},\mathrm{n})=\left\{\begin{array}{l}\mathrm{n}+1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}=0\\ \mathrm{A}(\mathrm{m}-1,1)\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}>0\text{and}\mathrm{n}=0\\ \mathrm{A}(\mathrm{m}-1,\mathrm{A}(\mathrm{m},\mathrm{n}-1\left)\right)\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}>0\text{and}\mathrm{n}>0\end{array}\right.$

Its value grows rapidly, even for small inputs.

A (0,1) = A (0,A(1,0))

= A (0,2)

= 3

Hence, the value is 3.

(d) Find  A (2,2)

There are several different variants of this function. All are calledAckermann’s functions and have similar properties even though their values do not always agree.

One common version, the two-argument Ackermann-Peter function, is defined as follows

For nonnegative integers m and n:

$\mathrm{A}(\mathrm{m},\mathrm{n})=\left\{\begin{array}{l}\mathrm{n}+1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}=0\\ \mathrm{A}(\mathrm{m}-1,1)\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}>0\text{and}\mathrm{n}=0\\ \mathrm{A}(\mathrm{m}-1,\mathrm{A}(\mathrm{m},\mathrm{n}-1\left)\right)\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{m}>0\text{and}\mathrm{n}>0\end{array}\right.$

Its value grows rapidly, even for small inputs.

By the above definition of Ackermann’s function,

$\begin{array}{r}\mathrm{A}(2,2)=\mathrm{A}(1,\mathrm{A}(2,1\left)\right)\\ =\mathrm{A}(1,\mathrm{A}(1,\mathrm{A}(2,0)\left)\right)\\ =\mathrm{A}(1,\mathrm{A}(1,\mathrm{A}(1,1)\left)\right)\\ =\mathrm{A}(1,\mathrm{A}(1,3\left)\right)\end{array}$

Now,

$\begin{array}{r}\mathrm{A}(1,3)=\mathrm{A}(1,3)\\ =\mathrm{A}(0,\mathrm{A}(1,\left)\right)\\ =\mathrm{A}(0,\mathrm{A}(0,\mathrm{A}(1,1)\left)\right)\\ =\mathrm{A}(0,\mathrm{A}(0,3\left)\right)\\ \mathrm{A}(1,3)=\mathrm{A}(0,(3+1\left)\right)\\ =\mathrm{A}(0,4)\\ =4+1\\ =5\end{array}$

Now we have,

$\begin{array}{r}\mathrm{A}(1,\mathrm{n})=\mathrm{n}+2\\ \mathrm{A}(1,5)=5+2\\ =7\end{array}$

Hence, the value is 7.