CS 5315 Homework #5

Date Assigned: Tuesday, February 1, 2005

Due Date: Tuesday, February 8, 2005 (extra credit if submitted by Thursday, February 3, 2005)

1. Describe, in detail, the proof that we went over in class again: that there exists a computable function which is not primitive recursive.

2. Let A(n) denote the Ackermann's function. We know that this function is computable but not primitive recursive. Let us take it as one of the basic functions to the definition of p.r. functions.

Namely, let us define the new notion of a A-primitive recursive function (A-p.r., for short) as follows: An A-p.r. function is any function that can be obtained from 0, successor function sigma, projection functions, and the Ackermann's function A(n) by using composition and primitive recursion.

Prove that there exists a computable function which is not A-primitive recursive.