Given two Turing Machines M1 and M2, we build a new machine M that does the following on input x:Run M1 on x. If M1 accepts x, then go to an accept state.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!
Language of a Turing Machine that runs its input on two other Turing Machines
formal languages;turing machines
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 thisM(x) =   repeat      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 repeatIf 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.