# The set of words accepted by TMs simultaneously is finite is non semi-decidable

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.

• 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$. – Andrej Bauer Aug 29 '17 at 10:35
• @AndrejBauer "at the same time" means that the word is accepted after n steps in both machines, you can assume they are deterministic... – Javier Aug 29 '17 at 10:53