Due by 2359 (11:59 PM) on Wednesday November 2. Hand in via Gradescope.

Note: For all problems, show your working and justify your answers. Upload all of your problems and working to the Gradescope assigment called “Full Paper Submission” .  Additionally, upload your final answers only to the Gradescope assignment called “Answer-check Submission” for those problems marked [ACS] below.

You will not receive points for submitting answer to the Answer-check Submission if you do not also upload your working to the Full Paper Submission.

You may discuss these problems among yourselves,  but your final submitted solutions must be written by you alone.

1.       Fix an enumeration u0 , u1 , . . .  of algorithms. Let h : N → N be the following function: h(n) =

Let f (n) = max0≤m≤n h(m).

(a)  Prove that f is not computable.

[You may use the fact from lectures that the halting function H0  is non-computable.]

(b)  Let F : N → N be any function such that F “eventually grows faster than f”: that is, there exists

N 2 0 such that for all n 2 N , F (n) 2 f (n).

Prove that F is not computable.

[In other words, “f grows faster than any computable function” .]

2.       I have invented a cool new programming language, a variant of Python called Termisnakes. It has the following cool features:—

.       Any valid Termisnakes program always terminates on every input.

.       You are given an enumeration t0 , t1 , t2 , . . . that contains all valid Termisnakes programs (and

no invalid ones).

The details are proprietary but you should imagine that Termisnakes only allows for loops with a bound on the number of iterations given in advance, rather than general while loops which could run forever.

We say a function N → N is  Termisnakes  computable  if there is a Termisnakes program whose output is that function.  (By construction, such functions are total.)

Let T : N × N → N denote the universal  Terminsnakes function T (n, a) = tn (a). Prove that T is not Termisnakes computable.