Given two Turing Machines M1 and M2, we build a new machine M that does the following on input x:

  1. Run M1 on x. If M1 accepts x, then go to an accept state.
  2. Run M2 on x. If m2 accepts x, then go to an accept state.

What would be the language of such a Turing Machine? My first intuition was that $L(M)=L(M1) \cup L(M2)$ , but this can't be the case since if $x \notin L(M1)$ and $x \in L(M2)$, then there is the possibility that M1 runs forever, so M2 will never get the chance to recognize x and go to an accept state.

Unless we assume that M1 never runs forever, how is it possible to express $L(M)$? Thanks!

  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Nov 12 '16 at 20:28

You're right: it might happen that $M_1$ might run forever on input $x$, so you'd never get to the "run $M_2$ on $x$" part. This problem goes away if $M_1$ and $M_2$ were deciders, i.e., if they are guaranteed to halt on any input in either an accept state or a reject state. In that case we would have $L(M)=L(M_1)\cup L(M_2)$ and would have proven that decidable (aka recursive) languages are closed under union.

All is not lost, though, to show that this holds for more general languages. Suppose that we know that we have languages $L_1,L_2$ such that there are TMs $M_1, M_2$ with $L_1=L(M_1)$ and $L_2=L(M_2)$. Then we can make a TM $M$ such that $L(M) = L_1\cup L_2$ by a very useful technique known as dovetailing, like this

M(x) =
      run M_1(x) for one move (beyond any that have been made already)
      if M_1 accepts
         return accept
      run M_2(x) for one move (ditto)
      if M_2 accepts
         return accept
   // end repeat

If either $M_1$ or $M_2$ accepts $x$ then it will do so in some finite number of moves, and that's all we need for $M$ to accept $x$. So for this machine, we'll have $L(M)=L(M_1)\cup L(M_2)$, exactly as needed.

  • $\begingroup$ So I can say that, unless M uses the dovetailing approach you described, L(M) is undefined. $\endgroup$ Nov 12 '16 at 22:00
  • $\begingroup$ @user1354784 Actually, you can say a bit more. Since the original machine $M$ tests input $x$ on $M_1$ before it tries $M_2(x)$, $M$ will accept any string that $M_1$ does, so we can at least say that $L(M_1)\subseteq L(M)$. There might be other strings in $L(M)$ but we can't say too much about them. $\endgroup$ Nov 13 '16 at 21:11

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.