# Reduction to proof undecidability of the problem: machine M and N accept infinitely many words

I am struggling with the following problem: Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and machine N. In other words, is language { encodedMachine(M)#encodedMachine(N) | intersection of language of M and language of N is infinite } decidable?

Intuitively it feels like this is undecidable problem and halting reduction might be used to proof this, but I have no idea how to start this reduction.

• Hint: Take $M=N$ to be machines ignoring their inputs. – Yuval Filmus Jun 22 '19 at 2:07
• Your problem is actually $\Pi_2$-complete, making it more difficult than the halting problem. – Yuval Filmus Jun 22 '19 at 2:08
• @Yuval Filmus, thank you for the tip, but I am not sure if I understand. Let's take a machine for example. Machine K and alphabet {a, b}. Machine K accepts any words made with a (a, aa, aaa, aaaa....), but it loops when first letter is b. So it doesn't have halting property, but it accepts infinitely many words. – Andy Jun 22 '19 at 10:00
• On the other hand, I also don't see how to distinguish answer "doesn't accept infinitely many words". Let's assume M loops always -> then it doesn't accept infinitely many words. Let's assume machine accepts word aba and rejects other words, then we get same answer it doesn't accept infinitely many words – Andy Jun 22 '19 at 10:02
• Or maybe I didnt understand the part machines ignoring their inputs.. Could you please elaborate on that? – Andy Jun 22 '19 at 10:05

For a TM $$M$$, let $$K$$ be the same as $$K$$ but ignoring inputs. That is, for any input, $$K$$ will first erase the input so that it looks like an empty input is given. Then $$K$$ will simulate $$M$$ on empty input. When the simulation halts, $$K$$ accepts. Now consider whether $$\langle K\rangle\#\langle K\rangle$$ is in the language specified in the question.
Exercise. Construction a reduction from the other halting problem, whether a given TM halts on a given input $$x$$.