1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$
    – frabala
    Commented Jul 21, 2020 at 9:43

0

Reset to default

Your Answer

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