Question

Show that any infinite subset of$MI{N}_{TM}$ is not Turing-recognizable.

Short answer

Infinite subset of$MI{N}_{TM}$ is not Turing-recognizable.

Step-by-step solution

Turing-recognizable

A language L is said to be Turing Recognizable if and only if there exist any Turing Machine (TM) which recognize it i.e., TM halt and accept strings belong to language L and will reject or not halt on the input strings that doesn’t belong to language L .

Proving infinite subset of MINTMis not Turing-recognizable

Let us assume an infinite set$MI{N_{TM}}^{*}$which is subset of i.e.,$MI{N_{TM}}^{*}\subset MI{N}_{TM}$ .

Also let us assume that$MI{N}_{TM}$is Turing-recognizable.

Then,$MI{N_{TM}}^{*}$can be computed using enumerator E . Let c is decider for$MI{N}_{TM}$ and we design c as follows:

• Obtain
• We will use E to create Turing Machine D$\in MI{N_{TM}}^{*}$ such that
• Run D

Now, we have Turing Machine D which simulates D for all its input. So D is equivalent to c , but we have stated that . This make our assumption contradicts as D comes to be minimal.

Thus, enumerator E will not exist, so $MI{N_{TM}}^{*}$which is infinite subset in$MI{N}_{TM}$ is not Turing-Recognizable.