CS 5315 Homework #4

Date Assigned: Thursday, January 27, 2005

Due Date: Tuesday, February 1, 2005

1. Describe the function div in terms of mu-recursion.

2. Show that the following function f(n) is mu-recursive: f(n)=5 for n=3, f(n)=7 for n=5, and f(n) is undefined for all other n.

3. Describe a Turing machine that computes the function f(n)=n+2.