Comp 230 Assignment 3

Chak Shan Chun 260321705

Comp 230 Assignment 3 1) Primitive Recursive Functions a. Show that if P and Q are primitive recursive conditions, then so are P ∧ Q, P ∨ Q, ⅂P, and P → Q.

b. Consider the primitive recursive definition of addition (see p.94) here rewritten in terms of function g and function h: Plus (0, x) Plus (n+1, x)

= =

g(x) h(Plus(n,x), n, x)

Where g(x) = P11 (x) and h(x,y,z) = S(P13 (x,y,z)). Given the numbering for primitive recursive functions described in Ch.11 F (P.103), what number is assigned to the function plus?

2) The μ- operator Explain in a brief paragraph why the μ- operator and the min-operator (both introduced on p.122-123) are not the same For μ- operator, it defines the first solution it finds for f(→ ,y)= 0 and returns that value. 𝑥

However, for every y less than that first solution, it must be always defined. Where as for the min-operator, it either finds a solution or goes on forever. If we were to use mu-operator, it ensures that all value before the first solution to zero is defined ie. a halting function otherwise, it will show that the function is undefined as there exist a value which causes the function to be undefined.

3) Partial Recursive Functions. a. Prove that K0 is not recursive

b. We said that we can’t diagonalize out of the class of partial recursive functions. But doesn’t the function f defined by 𝝋𝒙 𝒙 + 𝟏 𝒊𝒇 𝝋𝒙 𝒙 ↓ 𝒇 𝒙 = 𝟎 𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆 Diagonalize the class of partial recursive functions? Explain.

4) Listability; recursively enumerable sets. a. Prove that if A is recursive then both A and 𝑨 are r.e

b. Show that if A is r.e and can be enumerated in increasing order, then A is recursive.

5) Theorems. a. Explain Corollary 5a (p.134) and In programming terms, this would means that in order to solve a problem on a computer, instead of having different loops for different problems, we can just wrap up the all the algorithms with just one big loop as its check. b. Theorem 7 (p.135) A function F will have at least one fixed point where f(x) = x. (mapping to itself)

6) Universal Turing Machine Explain in a brief paragraph what a Universal Turing Machine is. If a Turing machine could calculate a function φ then the set of the quadruples of the machine can be converted into a partial recursive definition of φ (Pg146 of the textbook). Suppose a Universal Turing Machine exist, that means that its instruction can be converted into a partial recursive definition and we know from the lecture that such a universal computation function exists for all partial recursive functions. Hence, a universal turing machine is analogous to the universal computation predicate.

7) Philosophy of Mind. a. Write a brief argument supporting the claim that the human brain is equivalent to a Turing machine. Human brain is equivalent to a turing machine in the sense that human brain has different brain states which might change due to actions we made (which is equivalent to writing 1 or 0 or moving right or left) or observations we perceived (which is equivalent to the 0 or 1 the head is reading). Hence, human brain is equivalent to a Turing machine. b. Write a brief argument supporting the claim that the human brain is not equivalent to a Turing machine. We know too little about human brain to be making the assumption that human brain is equivalent to a Turing machine. For instance, we do not know how we could multitask, like watching tv while eating. This is not possible with Turing machine as turing machine process one instruction at a time but the fact that we could watch tv while correctly feed ourselves might suggest that we could simultaneously be in two or more brain states or be executing two or more instructions at a time.