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!
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?