3
$\begingroup$

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$
$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Kevin Goedecke Aug 8 '15 at 11:42
  • $\begingroup$ @KevinGoedecke That's a separate question, which you are welcome to ask. $\endgroup$ – Yuval Filmus Aug 8 '15 at 12:36
  • $\begingroup$ 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? $\endgroup$ – Kevin Goedecke Aug 8 '15 at 18:35
  • $\begingroup$ (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." $\endgroup$ – Yuval Filmus Aug 8 '15 at 21:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 9 '15 at 19:26

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.