Theoretical Computer Science (M21276)
Part B/2: Computability and Equivalent Models, Part 2
(Nov 29 – Dec 3, 2021)
Model 5: Partial recursive functions
Copyright By PowCoder代写 加微信 powcoder
Question 1. Using the primitive recursive function for addition (from Lecture) calculate
the value of 4 + 3 =. . .
add(x, 0) = x,
add(x, succ(y)) = succ(add(x, y))
Question 2. Show that the constant function f(x) = 4 is primitive recursive.
Question 3. Show that the function mul for multiplication of two natural numbers is primitive recursive. Try to experiment with mul(1, 0), mul(2, 0), . . . , mul(1, 1), mul(2, 1), ….
Show that 4 × 3 = 12.
Question 4. Show that the function pred which is defined by: 0 if x = 0
pred(x) = x − 1 otherwise. Using your definition calculate the value of pred(7) =. . .
is primitive recursive.
Question 5. If we want to define a subtraction, we need to stay within the domain of natural numbers. So, we define the operation “subtract as much as you can”, called monus. This operation is commonly written as −· and is defined by:
x−y ifx≥y
x −· y = 0 otherwise.
Formulate monus as a primitive recursive function and show that monus(6, 4) = 2. Question 6. Show that the following predicates are primitive recursive (hint: try to use
sign function)
(i) less(x,y)=‘ifx