(5 MARKS) Prove that the problem or ( C where C = {r : 42 ( ran(Or)} is semi-computable. Hint. Use closure properties of P. and the semi-recursiveness of Aryz.d, (y) = z from the Notes/Class/Text.7.3.2 Example. The set A = {(x, y, =) : or(y) = =} is semi-recursive. Here is a verifier for the above predicate: Given input r, y, z. Comment. Note that or(y) = z is true iff two things happen: (1) or(y) + and (2) the computed value is z. 1. Call the universal function h on input x, y. 2. If the Universal program H for h halts, then . If the output of H equals z then halt everything (the "yes" output). . If the output is not equal to z, then enter an infinite loop (say "no", by looping). By CT the above informal verifier can be formalised as a URM M. But is it correct? Does it verify or(y) = z? Yes. See Comment above.8.2.2 Theorem. P, is closed under A and V. It is also closed under ( By), or, as we say, "under projection". Moreover it is closed under (By)