TÖL203F Algorithms, Logic and Complexity

Homework 6

We have defined and looked at some examples of Abacus machines in Chapter 5. We then proved that any Abacus machine can be simulated by a Turing machine (5.2). Next week we will see that Abacus machines can compute any recursive function (5.3). Then we will also start on Chapter 6 on recursive functions.

Homework

  1. Problem 5.1 on page 61 in the textbook.

  2. Problem 5.2 on page 61 in the textbook.

  3. Show an Abacus machine to compute the factorial function, f(n) = n!.

  4. Problem 5.7 on page 62 in the textbook.
    Hint: You know the value of k when you build the Turing machine (i.e. one Turing machine doesn't have to work for all k).

  5. Problem 5.9 on page 62 in the textbook.

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

hh (hja) hi.is, February 7th, 2014.