The goal of this problem is to find an uncomputable (or “incalculable”) function

Question

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> | 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 that HALT TM is 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.

Explanation / Answer

a)
consider HALTtm = {<M,w> ; where M does not halt on w}.
M will halt on input epsilon only, otherwise it runs infinitely on other inputs.
If HALTtm is both recognisible and co-recognisible then M is considered to be decidable. But HALTtm
is not recognisible and HALTtm <= f(x). So S is not recognisible.

------------------------------------------------------------------------------------------------

b)
Let us assume HALT TM is decidable. We will try to prove this now.
TM is said to be decidable if it terminates on all inputs. But in our problem it halts only on
epsilon value. So our assumption went wrong. So HALTtm is not decidable.

--------------------------------------------------------------------------------------------
c)
Let Hn be set of n state.
Hn = {<M,m>}, n states.
m halts on epsilon.

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

Language L1 is said to be decidable, if halts on every input. Here in our case it will halt on
inputs 0 and 1 . It run infinite times. So L1 is not decidable

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.