Consider $L = \{(M_1,M_2):\text{the set of words accepted by both TM at the same time is finite}\}$. I want to determine if this language is decidable, semi-decidable or not semi-decidable.

My thoughts

My intuition tells me this is a nonRE language. Before, I showed that the same language considering the condition "there exists a word accepted by both" is semi-decidable. However, the condition of being finite is too much since one should check all the words accepted by the machine (in order to show that it is in fact finite).

Therefore, I think I have to try reductions of nonRE languages. I tried with $L_e$ machines that produce the empty set, but this condition doesn't seem to go well with the non-finiteness I need at some point of the implications.

Maybe you have some suggestions.

  • $\begingroup$ I do not understand your defintion because it use the word "time". Is it this: $ \{(M_1, M_2) \mid \text{$L(M_1) \cap L(M_2)$ is finite}\}$? Here $L(M)$ is the set of words accepted by $M$. $\endgroup$ – Andrej Bauer Aug 29 '17 at 10:35
  • $\begingroup$ @AndrejBauer "at the same time" means that the word is accepted after n steps in both machines, you can assume they are deterministic... $\endgroup$ – Javier Aug 29 '17 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.