TÖL203F Algorithms, Logic and Complexity

Homework 8

We have seen the minimization rule for recursive functions (6.2), and defined recursive sets and relations from Chapter 7. We defined the closure properties for recursive relations (7.1) and looked at some examples of recursive relations. Next week we will look at more examples and see semirecursive relations (7.2). Then we start on chapter 8 which shows that all three models of computation (Turing machines, Abacus machines and recursive functions) are equivalent.

Homework

  1. Problem 7.1 on page 86 in the textbook. You just have to show that if R is recursive then these relations are recursive.

  2. Problem 7.3 on page 86 in the textbook.

  3. Problem 7.5 on page 86 in the textbook.

  4. Let f(x, y) be the function below:

    Show that f is primitive recursive.

  5. On page 78 of the book there is a proof that Min[R] is a recursive function if R is a recursive relation. The proof for Max[R] is omitted in the book. Show this proof.

Hand this homework in before 12:00 on friday February 28th.

hh (hja) hi.is, February 21st, 2014.