Paper 4, Section I, 4 F4 \mathrm{~F}

Automata and Formal Languages
Part II, 2016

(a) Construct a register machine to compute the function f(m,n):=m+nf(m, n):=m+n. State the relationship between partial recursive functions and partial computable functions. Show that the function g(m,n):=mng(m, n):=m n is partial recursive.

(b) State Rice's theorem. Show that the set A:={nNWn>7}A:=\left\{n \in \mathbb{N}|| W_{n} \mid>7\right\} is recursively enumerable but not recursive.