TL203F Algorithms, Logic and Complexity

Homework 9

We have seen more examples of recursive sets and also seen semirecursive relations (7.2). We skipped section 7.3. Then we started on chapter 8 that shows how Turing machines can be simulated by recursive functions. Next week we will finish that and look at universal Turing machines (8.2).


  1. Problem 7.2 on page 86 in the textbook.

  2. Problem 7.8 on page 86 in the textbook. Hint: Use Corollary 7.8 in the book (i.e. minimization with a primitive recursive bound).

  3. This problem is about the coding method describe at the bottom of page 79 in the textbook.
    1. What would be the integer coding of the sequence (2, 0, 1, 4)?
    2. What is the sequence coded by the integer 9,845,600,625,000?

  4. Wang coding of a Turing machine tape is described on page 89 in the textbook. Assume that the value of p is 74 and the value of r is 8. Show the contents of the tape and the new values of p and r after the following transitions:
    1. Move left
    2. Write 1
    3. Move right

  5. If Turing machines were allowed to move (left or right) and write (1 or blank) in the same transition, how could we simulate those transitions using recursive functions? Use functions similar to those described on pages 90-91 in the textbook.

Hand this homework in before 12:00 on friday March 7th.

hh (hja), February 28th, 2014.