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 exist which will halt in finite amount of time.

Conditions on  P

There were two 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 have constructed Turing Machine that ensures that M is a valid Turning Machine description and accepts the input.

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

Proving P undecidable

Now, ifis the property of the machine, then P would be ‘Decidable’, but rather these properties is due to two conditions given, that makes P as undecidable.

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