# Proof by Turing Reduction

I need to proof the following by turing reduction.

Given two languages:

$Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$

$I= \{\langle M \rangle \mid \;\vert L(M) \vert = \infty \}$

Where $\langle M_1 \rangle$ is the encoding of Turing Machine $M_1$.

I need to show that $I \le_T Q$ ($I$ can be reduced to $Q$ using a Turing Machine).

So far I came up with the following idea, which I think isn't correct.

Create Turing Machine $M'$ so that a mapping from $Q$ to $I$ is found:

1. $M'$ takes as input a random word $u$ for example $aab$
2. $M'$ removes the input ($u$) from its tape
3. $M'$ guesses words $v$ and $w$
4. $M'$ checks if $v \in L(M_1)$ and $w \in L(M_2)$ if and only if $v = w$

Your solution doesn't quite make sense for many reasons:

1. The reduction should take $\langle M \rangle$ as input, and using an oracle to $Q$, decide whether $\langle M \rangle \in I$.

2. The reduction should be deterministic (so step 3 is invalid).

3. The function of the arbitrary word $u$ is not explained; indeed, steps 1 and 2 seem useless.

4. You don't explain what $M_1,M_2$ are in step 4 (are you trying to reduce from $Q$ to $I$?).

5. You don't explain how to implement step 4.

Also, you are missing a proof that your reduction works. Without a proof, your solution is wrong even if it could be completed to a correct solution.

One solution goes along the following lines (I'm assuming $L(M)$ consists of all inputs on which $M$ halts; I also say that $n \in L(M)$ is accepted by $M$):

1. Given $M$, let $M'$ be the machine that on input $n$, simulates $M$ on $n$, and then (if $M$ halted) tries to find an $m > n$ accepted by $M$ (if there is no such $M$, it never halts); you can implement this using the technique of dovetailing.

2. Give $M$ and $M'$ to the $Q$ oracle, and return its answer.

The idea is that $L(M)$ is infinite iff $L(M) = L(M')$. I'll leave you the details.

• Thanks a lot for your help. I am actually also interested in how the reduction from $Q$ to $I$ would look like, can you point out a way for that too? – Kevin Goedecke Aug 8 '15 at 11:42
• @KevinGoedecke That's a separate question, which you are welcome to ask. – Yuval Filmus Aug 8 '15 at 12:36
• So let me get this straight: I build a new TM $M'$ which takes $n$ as an input (what is $n$ here?) and internally runs $M$ (here $I$?), let me call it $M_I$, as a subprogram. Now when the subprogram $M_I$ halts on n, it will look for an $m > n$ through dovetailing. Thus the language is infinite. I dont really understand on how I can pass $M'$ to the oracle to check if its $\in Q$. Can you maybe help me out here too? – Kevin Goedecke Aug 8 '15 at 18:35
• (1) I denote the input to $M'$ by $n$. So $n$ is just the name I use for the input. (2) $M$ itself (or rather, $\langle M \rangle$) is the input to the reduction. It's an instance of $I$. (3) You can pass $M$ and $M'$ (or rather, $\langle M \rangle$ and $\langle M' \rangle$) to the oracle since that's one of the instructions that an oracle Turing machine can do. (In this particular instance, the reduction is actually a many-one reduction, if you know what that means.) (4) I don't understand what you mean by "Thus the language is infinite." – Yuval Filmus Aug 8 '15 at 21:03
• That's exactly what the oracle does. In this case, given $\langle M \rangle$ and $\langle M' \rangle$ it tells you whether $L(M) = L(M')$ or not. – Yuval Filmus Aug 9 '15 at 19:26