Exercise 1 (The Ackermann function). The Ackermann function is a very important function in theoretical computer science and logic. It is a two-variable function A:N ? N defined recursively by the following conditions: (1) A(0, y) = y +1 for every y EN, (ii) A(n +1,0) = A(n,1) for every n e N, (iii) A(n +1, y + 1) = An, A(n +1, y)) for every n, Y EN. The theoretical importance of the Ackermann function is the following: For any primitive recursive function F:N + N, there is a ficed nf EN such that F(2) An, 2) + y. Hint: do induction first on n, then on y. (4) For every n, y EN, if n > 1, then An +1,y) > An, y) + y. Hint: do a similar type of double-induction as in (3). (5) For every n, y eN, A(n +1, y) > An, y + 1). Hint: do induction on y. (6) For every n,y e N, 2An, y) 0 use (3), (4), and (5) above. (7) For every n, 2, Y EN, if