Why is the following language undecidable?

Question

I'm currently learning for my exams this semester and tried to solve some old exams from the last years.

The question is to show, that L ist undecidable. $L=\{w|T(M_w)\neq\emptyset \land \forall x \in T(M_w): xx\in T(M_w)\land xxx\notin T(M_w)\}$

I showed that the language $L'=\{w | T(M_w)\neq \emptyset\}$ is undecidable due to the Rice Theorem. I created to Turing Machines $M_1$ with $T(M_1)=\emptyset$ and $M_2$ with $T(M_2)=\Sigma^*$ to show that the language L' is not trivial. (since $1\in L$ and $2\notin A$. With out loss of generality i assume those machines have the Gödelindexes 1 and 2)

My problem now is, that I know no way to show, that this result transfers to the language L. I know that the language L must only contain such Gödel Indexes, that for those indexes the following TM must accept infinite words (because in case of $x\in T(M_w)$ there must be $xx\in T(M_w)$... and therefore must be $xxxx\in T(M_w)$ etc.)

I would love to hear suggestions / answers! Thanks in advance

Answer 1

This is a direct consequence of Rice's theorem. A word $w$ is in $L$ if $T(M_w)$ satisfies the following semantic property:

$T(M_w)$ is non-empty, and for any $x \in T(M_w)$, we have $x^2 \in T(M_w)$ and $x^3 \notin T(M_w)$.

In order to show that this language is undecidable according to Rice's theorem, we need to exhibit two Turing machines $w_1$ and $w_2$: one which doesn't satisfy the property, and another one which does satisfy it. We can take $w_1$ to be some machine such that $T(M_{w_1}) = \emptyset$, and $w_2$ to be some machine such that $T(M_{w_2}) = \{ a^{2^n} : n \geq 0 \}$.