# How to conceive a Turing machine that is the intersection of the languages of two Turing machines?

We have $$M = (Q,Σ,Γ,δ,q_0,q_a,q_r)$$ and $$M′= (Q′, Σ , Γ′, δ′,q_0′,q_a′,q_r′)$$.

We want to construct a standard Tm that recognize L(M) ∩ L(M′). How do I go about it? I don't have much more information than this. Anything to get started would be appreciated.

• Its the same proof as for regular languages. Check that out first (under "closure properties of regular languages") – nir shahar Jul 4 at 21:23

What you ask might not be possible in general. If $$L(T)$$ denotes the set of words $$x$$ for which $$T(x)$$ accepts, and you do not have the additional assumption that $$M$$ and $$M'$$ recognize $$L(M)$$ and $$L(M')$$, respectively, then you could choose:

• $$M$$ as a Turing machine that takes another Turing machine $$T$$ as input and accepts if and only if $$T$$ halts on empty input. (Notice that such a Turing Machine $$M$$ exists).
• $$M'$$ as a Turing Machines that recognizes $$\Sigma^*$$.

Then, there is no Turing Machine $$T$$ that recognizes $$L(M) \cap L(M') = L(M)$$ since $$T$$ would solve the halting problem.

On the other hand, if you are fine with a Turing machine that accepts $$L(M) \cap L(M')$$ or if you have the additional assumption that $$M$$ and $$M'$$ recognize $$L(M)$$ and $$L(M')$$, respectively, your problem is solved by a Turing machine that, on input $$x$$, operates as follows:

• Simulate $$M(x)$$ until it halts (possibly never).
• If $$M(x)$$ rejects, reject.
• Simulate $$M'(x)$$ until it halts (possibly never).
• If $$M'(x)$$ rejects, reject.
• Accept.
• @Evil, thank you! I fixed the symbol. – Steven Aug 5 at 22:50