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.
b
. So it doesn't have halting property, but it accepts infinitely many words. $\endgroup$ – Andy Jun 22 '19 at 10:00aba
and rejects other words, then we get same answerit doesn't accept infinitely many words
$\endgroup$ – Andy Jun 22 '19 at 10:02machines ignoring their inputs.
. Could you please elaborate on that? $\endgroup$ – Andy Jun 22 '19 at 10:05