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. Answer: f(x) = succ(succ(succ(succ(zero(x)))))
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.
Answer: mul(x, 0) = 0, mul(x, succ(y)) = add(x, mul(x, y)). add(n1,n3). Using projection functions, we can write this as: g(n1, n2, n3) = add(pr13(n1, n2, n3), pr3(n1, n2, n3)).
And g(n1, n2, n3) =
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.
Answer: pred(0) = 0, pred(succ(x)) = x
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. Answer: monus(x, 0) = x, monus(x, succ(y)) = pred(monus(x, y))
Question 6. Show that the following predicates are primitive recursive (hint: try to use sign function)
(i) less(x,y)=‘ifx