The goal of this problem is to find an uncomputable (or incalculable) function. This function, S(n), will grow so fast that even Turing machines cannot keep up with it.

Let -HALT TM = { | M is a TM and M halts on the input (i.e. no input)}.

You can assume the input alphabet to be = {0, 1}, which is sufficient to encode M.

a) Is -HALT TM recognizable? Why or why not?

b) Prove that -HALT TM is not decidable. Hint: you can use the fact thatHALT TMis not decidable and use that to show that -HALT TM being decidable would lead to a contradiction.

c) Let Hn be the set of n-state TMs that eventually halt when run on the empty input.Let S(n) be the maximum number steps a TM in Hn can take.

Let L1 = {m | m {0, 1}* such that m = S(n) for some n 1}.

Prove that L1 is not decidable.