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.
Homework
[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.
[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
Problem 6.1 on page 71 in the textbook.
Problem 6.3 on page 72 in the textbook.
Problem 6.8 on page 72 in the textbook.
Hand this homework in before 12:00 on friday February 21st.