Abstract Algebra: Theory and Applications · Problem 2.5.2

Groups — Thomas Judson

Mathematics — Abstract Algebra · ackermann-function-programming

Problem

Let N0=N∪{0}\mathbb{N}^0 = \mathbb{N} \cup \{0\}. Ackermann's function is the function A:N0×N0→N0A : \mathbb{N}^0 \times \mathbb{N}^0 \to \mathbb{N}^0 defined by the equations A(0,y)=y+1,A(0, y) = y + 1, A(x+1,0)=A(x,1),A(x+1, 0) = A(x, 1), A(x+1,y+1)=A(x,A(x+1,y)).A(x+1, y+1) = A(x, A(x+1, y)). Use this definition to compute A(3,1)A(3,1). Write a program to evaluate Ackermann's function. Modify the program to count the number of statements executed in the program when Ackermann's function is evaluated. How many statements are executed in the evaluation of A(4,1)A(4,1)? What about A(5,1)A(5,1)?

Browse the problem library