Do the following.

$($a$)$ Provide the instructions of the URM program P that computes the function f$($n$)=$ n$2.$ Use the online URM simulator to verify that your URM is correct. $(10$ pts$)$

$($b$)$ Briefly describe the idea behind your program and the purpose of each register. $(10$ pts$)$

$2.$ Prove that the $\backslash$pi encoding function described in lecture is a one$-$to$-$one correspondence between N$\backslash$times N andN. Hint: foreachz in N$,$showthatthereisauniquepair$($x$,$y$)$ in N$\backslash$times N for which $\backslash$pi $($x$,$ y$)=$ z$.(15$ pts$)$

$3.$ Do the following.

$($a$)$ ProvidetheG $$odelnumberefortheprogramP $=$J$(1,2,7),$S$(2),$S$(2),$S$(2),$S$(3),$J$(1,1,1),$T$(3,1).$

Write e as a sum of powers of two minus one. $(10$ pts$)$

$($b$)$ Apply the decoding functions to e in order to verify that your answer to part a is correct.

Show all work. $(10$ pts$)$

$($c$)$ Describe $\backslash$phi e$($x$),$ We$,$ and Ee$.$ Justify your answers. $(10$ pts$)$

$4.$ Prove that there is a total computable function h$($n$)$ for which, for all n $>=0,\backslash$phi h$($n$)($x$)=$ xn$.$ Hint: you may assume that xn is a computable function of two variables. $(15$ pts$)$