# Decidability for $\exists w´, w´´\in L:$ so that |w´´| - |w´| is prime

I tried to decide wheter the given Language $$L = \{ \langle M \rangle | M \space is \space TM \space and \space \exists \space w´,w´´\in L(M):|w´´|-|w´| \space is \space prime \}$$ is recursive or recursive enumerable.

I tried to prove not recursive (undecidability) through Rice's theorem, since there exists $$M_1, M_2$$ so that $$L(M_1) = \{ a, aaaa \}$$ and $$L(M_2) = \{ a \}$$ and $$L(M_1) \in S \space and \space L(M_2) \notin S$$

So then for recursive enumerable (semi-decidability) I tried to show through constructing a TM. Given a computable sequence of $$w_1, w_2,... \in \Sigma^*$$ I would run the first i words on M for i steps, i+1 words for i+1 steps and so on and every word which is in the Language, I would put it on a different tape and with every word which comes to the tape I would try on another tape for every pair $$(i, j) \in \mathbb{N}$$ wheter $$|w_i|-|w_j|$$ is prime. So if w´ and w´´ exist I would find them in finite time.

Do you think that this might work for the proof? Any thoughts or improved solutions on this one?

• It looks ok, I believe. Rice's theorem is applicable here indeed because it regards a non-trivial and semantic property (a property over languages, not over TMs per se). Also, the process you describe in the last paragraph is terminating on each iteration $i$. – frabala Jul 21 '20 at 9:43