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

b.

Suppose HALT R and MH decides HALT. We construct a TM MBTH(M) to decide BTH. On input M, MBTH first constructs a new TM T that halts if M() halts and loops otherwise. MBTH then returns MH(T ). Since T is in HALT exactly when M() halts, MBTH decides BTH. But since BTH is undecidable, HALT must also be undecidablw

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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