Question

Use Rice’s theorem, which appears in Problem 5.28, to prove the undecidability of each of the following languages.

1. 
   
2. role="math" localid="1663214080203" ${\mathit{L}}_{\mathbf{T}\mathbf{M}}\mathbf{=}\mathbf{\{}\mathbf{<}\mathbf{M}\mathbf{>}\overline{)\mathbf{M}\mathbf{}\mathbf{i}\mathbf{s}\mathbf{}\mathbf{a}\mathbf{}\mathbf{T}\mathbf{M}\mathbf{}\mathbf{and}\mathbf{}\mathbf{1011}\mathbf{\in }}\mathbf{L}\mathbf{\left(}\mathbf{M}\mathbf{\right)}\mathbf{\}}$
   
3. $\mathit{A}\mathit{L}{\mathit{L}}_{\mathbf{TM}}\mathbf{=}\mathbf{\{}\mathbf{<}\mathbf{M}\mathbf{>}\overline{)\mathbf{M}\mathbf{}\mathbf{is}\mathbf{}\mathbf{a}\mathbf{}\mathbf{TM}\mathbf{}\mathbf{a}\mathbf{n}\mathbf{d}\mathbf{}}\mathbf{L}\mathbf{\left(}\mathbf{M}\mathbf{\right)}\mathbf{=}{\mathbf{\sum }}^{\mathbf{*}}\mathbf{\}}$
   

Short answer

1. INFINITE_TM is undecidable.
2. L_TM is undecidable
3. ALL_TM is undecidable.

Step-by-step solution

Undecidable

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

Solution (a)

We know that INFINITE_TM is the language for Turning Machine descriptions. It will satisfy two conditions of Rice’s Theorem which are as follows:

• First, P is nontrivial—it contains some, but not all, TM descriptions
• Second, P is a property of the TM’s language—whenever L(M₁) = L(M₂), we have $\left(M_1\right)\in P$iff $\left(M_2\right)\in P$

Now if there are two Turing Machine M₁ and M₂ and both can recognize same language. In such case, either both must have descriptions in INFINITE_TM or none of them have.

Therefore, we say that Rice’s Theorem indicate that INFINITE_TM is undecidable.

Solution (b)

Let us rewrite the statement as:

We need to prove that L_TM is undecidable.

Let us assume that L_TM is decidable. If that so, then there must be a Turing Machine R that will decide L_TM . We will use A_TM and reduced it to R. Now, using R to construct Turing Machine M' that can decide A_TM .

M' = on input (M, w)

• On input x
  Run on w.
  If accepts w, then accept if$x\in 1011$

• If accepts, means$1011\in L(M\text{'})$
  Else
  Means$1011\notin L(M\text{'})$

In order to decide A_TM, we will construct Turing Machine M' such that:

M' = on input (M,w)

• Run on input (M)
  If accepts (M') then accepts.
  Else
  Reject

Now, we know that A_TM is undecidable, so R cannot decide it. This means R cannot exist.

Hence, L_TM is undecidable.

Solution (c)

Let us assume that ALL_TM is decidable and is decided by Turing Machine R.

We will construct Turing Machine M' as follows:

M' = on input (M,w)

On input x

• Run M on x
  M accepts w, Accept.

Now, if M accepts wthen,

$L\left(M\text{'}\right)={\sum }^{*}$

But if M rejects w then,

$L\left(M\text{'}\right)=\varnothing$

We will create Turing Machine

On input (M, w)

• Construct Turing Machine M'
• Run R on M'.
  If R accepts M', Accept
  Else
  Reject

Now, since A_TM is undecidable, so R must not exist.

Since, no Turing Machine R exist that decide A_TM , therefore ALL_TM is undecidable.