Theory of Computation
Quiz 2, February 16, 2010

1. Prove that the function f(n) which is equal to n + 1 for even n and is undefined for all odd n is mu-recursive.

2. Based on the Turing machines for computing n + 1 and n - 1 given below, design a Turing machine for computing the composition (n - 1) + 1. Check it for n = 0 and for n = 2.

 (start, #) --> (move, R)        (start, #) --> (move, R)
 (move, 1)  --> (move, R)        (move, 1)  --> (move, R)
 (move, #)  --> (back, 1, L)     (move, #)  --> (erase, L)
 (back, 1)  --> (back, L)        (erase, 1) --> (back, #, L)
 (back, #)  -->  halt            (back, 1)  --> (back, L)
                                 (back, #)  -->  halt
                                 (erase, #) -->  halt