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