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


1 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 \}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.