1
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Hint: Take $M=N$ to be machines ignoring their inputs. $\endgroup$ – Yuval Filmus Jun 22 '19 at 2:07
  • $\begingroup$ Your problem is actually $\Pi_2$-complete, making it more difficult than the halting problem. $\endgroup$ – Yuval Filmus Jun 22 '19 at 2:08
  • $\begingroup$ @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. $\endgroup$ – Andy Jun 22 '19 at 10:00
  • $\begingroup$ 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 $\endgroup$ – Andy Jun 22 '19 at 10:02
  • $\begingroup$ Or maybe I didnt understand the part machines ignoring their inputs.. Could you please elaborate on that? $\endgroup$ – Andy Jun 22 '19 at 10:05
1
$\begingroup$

Here is the reduction from the halting problem, whether a given TM halts on empty input, as given in Yuval's comment.

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.