Rice's theorem application on a language that resembles ETM

Question

I'm working on an exercise that involves checking if the Rice's theorem can be applied on a two languages.

The first language is $E_{TM} = \{ \langle M \rangle \text{ | M is a Turing Machine and } L(M) = \emptyset \} $.

I already know it's undecidable, thus Rice's theorem should apply without any problem and in fact it checks the three theorem's requisite just fine.

The second language is $X = \{\langle M \rangle \text{ | M is a Turing Machine that does not halts on any input string \}}$.

To me, the fact that the TM does not halts on any string means that the language is empty, which means that X is similar if not equal to $E_{TM}$.

But the property stated in X is not on the language of the TM, but rather describes what it does on all possible strings.

Is this reasoning correct?

Thanks for your help.

Answer 1

First of all, note that there are undecidable languages where Rice's theorem cannot be applied. In your third paragraph one may suggest that it would work that way. But in fact, for $E_{TM}$ you can apply the theorem.

$X$ is not the same language as $E_{TM}$ but it is a proper subset of $E_{TM}$. E.g. the TM $M_0$ that prints $0$ (reject) immediately after the start for any input and halts after that is in $E_{TM}$ but not in $X$. However, Rice's theorem is applicable for $X$. You have to find a proper, non-empty subset of all computable functions $\mathcal{R}$ that contains precisely the function computed by the TM in $X$. Let $$\mathcal{S} = \{f_M \mid f_M(x) = \bot \text{ for all } x \in \{0, 1\}^\ast\},$$ where $\bot$ means "never halt". Then

• $\mathcal{S} \neq \varnothing$ as the function of the Turing machine that immediately goes in an infinite loop is in $\mathcal{S}$,
• $\mathcal{S} \neq \mathcal{R}$ as $M_0$'s function (see above) is not in $\mathcal{S}$.

Obviously, the set of all Turing machines that compute a function from $\mathcal{S}$ coincide with $X$. Thus, $X$ is undecidable following Rice's theorem.

Note that Rice's theorem can be stated in different ways but it should look like this when speaking about TMs.