## 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.