TL203F Algorithms, Logic and Complexity

Homework 7

We have seen this week that Abacus machines can compute any recursive function (5.3). Then we defined formally the primitive recursive functions (6.1). Next week we will see the minimization rule (6.2), and define recursive sets and relations from Chapter 7.


  1. [Exam 2013] Show an abacus machine to compute the function f(x)=floor(√x), i.e. the largest integer ≤ the square root of x. You can use abacus machines from the textbook as blocks in your diagram. Also describe in words how your machine works.

  2. [Exam 2013] Show that the following function is primitive recursive (by using previously defined primitive recursive functions):
                  / √x          if √x is an integer
          f(x) = |
                  \  0          otherwise

  3. Problem 6.1 on page 71 in the textbook.

  4. Problem 6.3 on page 72 in the textbook.

  5. Problem 6.8 on page 72 in the textbook.

Hand this homework in before 12:00 on friday February 21st.

hh (hja), February 14th, 2014.