Counterexample for the reverse implication of Rice's theorem

Question

Here is the version of Rice's theorem I use:

Rice's first Theorem: For every non-trivial, language invariant property $P$ of a set of Turing machines it holds that the set $$\{M | P(M) \}$$ is undecidable.

So my question is really is this give an example of a property $P$ of Turing machines that does not satisfy Rice's theorem and such that $$\{M | P(M) \}$$ is an undecidable language.

I was thinking about something like this: A Turing machine has property P if the computation history of input $\epsilon$ passes through 3 different states. This property is not language invariant but I cannot prove that it is undecidable...

For those wondering: by language invariant I mean the following: A property $P$ of Turing machines is called language invariant if $$L_{M1} = L_{M_2} \Rightarrow P(M_1) = P(M_2).$$ Thanks!

Answer 1

Your approach probably works. By that, I mean that your language will indeed be undecidable . . . if we replace "$3$" by a sufficiently large number. Maybe (probably?) $3$ is already large enough, but that would take some work.

The point would be to build for each $n$, a machine $M_n$ which basically (using a fixed number $k$ of states, independent of $n$) checks whether $n$ is in the Halting Problem. If $n$ is not in the Halting Problem, $M_n$ never uses more than $k$-many states. If $n$ is in the Halting Problem, have $M_n$ enter a subroutine where it goes through $k+1$ "dummy" states.

Basically, all we need is for there to be a universal Turing machine with $k$ many states. This is possible for large enough values of $k$; whether $k=3$ depends on exactly how you've set up your Turing machines. I believe under most definitions, 3 is indeed enough, but it would take an argument.

---

Here's a simpler approach. By the Padding Lemma, we can find a computable set $X$ of machines which each compute the empty language. (Note that of course $X$ doesn't consist of all machines computing the empty language.) Then any infinite subset of $X$ which is not all of $X$ will be non-language-invariant.

So: does $X$ have any non-computable subsets?

Answer 2

Here is an even simpler example. Take any non-trivial language-invariant property $P$ of Turing machines! Let $F$ be your favourite Turing machine (just one)! Let $S = \{ M : P(M) \oplus M = F \}$. Then $S$ is undecidable because $\{ M : M \in S \oplus M = F \} = \{ M : P(M) \}$ is undecidable by Rice's theorem. Done!

---

In general you can replace "$M = F$" by any non-trivial decidable statement. In other words let $S = \{ M : P(M) \oplus Q(M) \}$ where $Q$ is any computable property. Then $Q$ would not be language-invariant by Rice's theorem and hence $S$ also would not be language-invariant. But by the same argument as before, $S$ would be undecidable.

---

This motivates a more interesting question of whether there is a property of Turing machines that is not decomposable into $P \oplus Q$ where $P$ is a language-invariant property and $Q$ is a computable property. This is not hard to answer. We will start with no commitment for the desired property $I$, and incrementally commit some Turing machines to satisfy $I$ and some to not satisfy $I$, and never change our mind on previous commitments. Go through each computable property $Q$ one by one. We ensure the invariance that we have only made finitely many previous commitments at every step. We choose two Turing machines $A,B$ that are not already involved in previous commitments and either both satisfy $Q$ or both do not satisfy $Q$. This is possible by the invariance. If $A,B$ accept the same language, we commit $I(A)$ and $\neg I(B)$, otherwise we commit $I(A)$ and $I(B)$. In either case $I \oplus Q$ is not language-invariant. At the end of the process, $I$ is an example of the desired kind of property.