Question

A Turing machine that halts on all inputs is called a halting Turing machine (also known as Decider). Prove the following:

(a) If M1 and M2 are two halting Turing machines, then there exists a halting Turing machine that recognizes L(M1) ∩ L(M2).

(b) If M1 and M2 are two (not necessarily halting) Turing machines, then there exists a Turing machine that recognizes L(M1) ∩ L(M2).

Answer 1

a)

Given,

M1 and M2 are two halting Turing machines.

So, let's assume there is a turing machine M which accepts the intersection of both the machines M1 and M2.

Let there be a string which is passed on the turing machine M as follows :

In the above figure, when the string is passed through the turing machine M, it first reaches turing machine M1. if M1 rejects the string, then it goes to the reject state. If it is accepted by turing machine M1, then the string is passed to turing machine M2. If M2 rejects the string, then it goes to the reject state . If the string is accepted by the turing machine M2, then the it goes to the accept state of turing machine M.

This infers that the output of the turing machine M has only 2 options that is either it accepts a string which comes under the intersection of the languages of turing machine M1 asnd M2  or rejects it. So, the assumption that the turing machine M is a halting turing machine is correct.

Thus, there exists a halting turing machine M whose language is able to recognize the intersection of the languages of halting turing machine M1 and M2.

b)

Let's assume that there exist a turing machine M ( not necessarily halting turing machine ) that accepts the set of strings coming under the intersection of the languages accepted by turing machine M1 and turing machine M2 ( not necessarily halting turing machine ).

Let there be a string that is passed to the turing machine M as follows :

In the above figure, when the string is passed through the turing machine M, it first reaches turing machine M1. If M1 rejects the string, then it goes to the reject state . If M1 loops the string for an indefinite time then it goes to the looping state. If the string is accepted by turing machine M1, then the string is passed onto turing machine M2. If M2 rejects the string, then it goes to the reject state of turing machine M. If M2 loops the string for an indefinite time then it goes to the looping state .

This infers that the output of turing machine M has 3 options that is either it accepts it, rejects it or goes for a loop.

So, the assuption that there exist a turing machine M ( not necessarily halting turing machine ) that accepts the set of strings coming under the intersection of the languages accepted by turing machine M1 and turing machine M2 ( not necessarily halting turing machine ).

Thus, there exists a turing machine M whose language is able to recognize the intersection of the languages of turing machine M1 and M2.