Question

Question: Show that both conditions in Problem 5.28 are necessary for proving that P is undecidable.

Short answer

Language P is undecidable.

Step-by-step solution

Undecidability

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

Conditions on P

There are two given conditions:

• Condition (1): P is nontrivial—it contains some, but not all, TM descriptions.
• Condition (2): P is a property of the TM’s language—whenever $L\left(M_1\right)=L\left(M_2\right)$, we have$\left(M_1\right)\in P$ iff $\left(M_2\right)\in P$.

In Condition (1), we construct a Turing Machine that ensures that M is a valid Turning Machine description and accepts the input.

In Condition (2), we construct a Turing Machine that will reject all the strings.

Proving P undecidable

Now, if P is the property of the machine, then P would be “Decidable,” but these properties are due to two conditions given, which makes P undecidable.

Hence, both the conditions are necessary for proving that P is undecidable.