TÖL203F Algorithms, Logic and Complexity
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.
- Problem 5.1 on page 61 in the textbook.
- Problem 5.2 on page 61 in the textbook.
- Show an Abacus machine to compute the factorial function, f(n) = n!.
- 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).
- 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.