Consider the following inductive definition of a version of

Consider the following inductive definition of a version of Ackermann\'s function: A(m, n) = {2n if m = 0 0 if m Greaterthanorequalto 1 and n = 0 2 if m Greaterthanorequalto 1 and n = 1 a(m - 1, A(m, n - 1) if m Greaterthanorequalto 1 and n Greaterthanorequalto 2 Find the following values of the Ackermann\'s function: A(1, 3) = A(0, 1) = A(0, 2) = A(0, 3) = A(1, 1) = A(3, 3) =

Solution

(a) A(1,3)

Here m = 1 and n = 3

m= 1 >=1 and n = 3 >= 2

Given that A(m,n) = A(m-1,A(m,n-1)) if m>= 1 and n >= 2

So, A(1,3) = A(1-1,A(1,3-1))

A(1,3) = A(0,A(1,2)) ... (1)

In A(1,2) , m=1 and n=2

So, A(1,2) = A(1-1,A(1,2-1))

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

In A(1,2) , m=1 and n=1 this satisfies A(m,n) = 2 if m >= 1 and n = 1.

So,  A(1,2) = A(0,A(1,1))

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

Here m =0 and n = 2 which satisfies A(m,n) = 2n if m = 0.

So, A(1,2) = A(0,2)

      A(1,2) = 2*2 = 4 ..... (2)

Putting (2) in (1), we get

   A(1,3) = A(0,A(1,2))

   = A(0,4)

In A(0,4), m= 0 and n = 4, which satisfies A(m,n) = 2n if m=0.

So, A(1,3) = A(0,4)

   = 2*4

   = 8

So, A(1,3) = 8

(b) A(0,1)

Here m = 0 and n = 1 which satisfies A(m,n) = 2n if m = 0.

So, A(0,1) = 2*1 = 2

So, A(0,1) = 2

(c) A(0,2)

Here m = 0 and n = 2 which satisfies A(m,n) = 2n if m = 0.

So, A(0,2) = 2*2 = 4

So, A(0,2) = 4

(d) A(0,3)

Here m = 0 and n = 3 which satisfies A(m,n) = 2n if m = 0.

So, A(0,3) = 2*3 = 6

So, A(0,3) = 6

(e) A(1,1)

Here m = 1 and n = 1 which satisfies A(m,n) = 2 if m>=1 and n = 1.

So, A(1,1) = 2