TÖL203F Algorithms, Logic and Complexity
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).
- Problem 7.2 on page 86 in the textbook.
- 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).
- This problem is about the coding method describe at the bottom of page 79 in the textbook.
- What would be the integer coding of the sequence (2, 0, 1, 4)?
- What is the sequence coded by the integer 9,845,600,625,000?
- 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:
- Move left
- Write 1
- Move right
- 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) hi.is, February 28th, 2014.