Theory of Computation
Quiz 1, February 11, 2010

1. Prove that the function f(n) which is equal to 1 for n = 0, to 2 for n = 1, and is undefined for all other n is mu-recursive.

2. Design a Turing machine for computing the function identically equal to 1, i.e., a function that returns 1 for every input.