1
$\begingroup$

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 \}$

I'm trying to Turing reduce $Q$ to $I$ ($Q \le_T I$), not the other way around as solved here

Any ideas on how to solve this? What exactly will the Turing machine do here and which part is getting solved by the mysterious Oracle?

Improve this question
$\endgroup$
2
  • $\begingroup$ @DavidRicherby, that question asks on the other direction $I \le Q$, and a comment there asks the OP to post a new question if he wants to ask about the $Q\le I$ direction. $\endgroup$
    – Ran G.
    Commented Aug 8, 2015 at 16:24
  • $\begingroup$ @RanG. Ah, that's what I didn't spot. The edit makes that clear. $\endgroup$
    – David Richerby
    Commented Aug 8, 2015 at 17:35

1 Answer 1

Reset to default
4
$\begingroup$

Given $M_1$ and $M_2$ you construct a machine $M$ that on input $w$ does the following:

  1. it runs $M_1$ on the first $w$ inputs ($\epsilon$,0,1,00,01,..) for $w$ steps each.
    1. if $M_1$ accepts some input, you run $M_2$ on the same input and check it accepts too. (note, $M_2$ may not halt!)
    2. If $M_1$ rejects some input, you run $M_2$ for $w$ steps and verify it doesn't accept during that time.
  2. you do the same with $M_2$: run $w$ steps on each of the first $w$ inputs, and verify everything works, or reject otherwise
  3. if all checks pass - accept. Otherwise reject.

The idea is the following: as long as $M_1$ and $M_2$ behave the same, you will keep accepting all $w$'s. but as long as you find a difference, then you will reject that $w$ and all inputs $w'>w$, thus the accepted language becomes finite. You should be careful because machines may not halt. For instance, $M_1$ may reject some input, but $M_2$ won't halt on it -- still, they both "reject" it, and this case should be carefully analyzed.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can I put it like this? Please correct me if I'm doing something wrong: Create TM $M'$ that runs $M$ here for $Q$ as a subprogram. It takes input $w$ and checks if $M_1$ accept and then if the same $w$ gets accepted by $M_2$. Also if $w$ gets rejected by $M_1$ double check if it gets rejected by $M_2$. Do the same thing vice verse with $M_2$ as described by you in (1.) and (2.). How does this now proof that $\in I$? Can I just ask an oracle $I$ if $\in I$? $\endgroup$
    – Kevin Goedecke
    Commented Aug 8, 2015 at 19:01
  • $\begingroup$ I think you can do without the second part of step 1, since this will be checked by step 2 (and conversely for the implicit second part of step two). --- I do not understand what problem there is with halting in your last two sentences. If one accept and the other rejects or does not halt, you have a difference and not halting is the proper behavior. $\endgroup$
    – babou
    Commented Aug 8, 2015 at 22:52
  • 1
    $\begingroup$ @KevinGoedecke Try to understand what is written, The idea of the proof is as follows. Suppose $v$ is a number that belongs to one language and not the other, and $n$ is the number of steps needed by the machine $M_1$ or $M_2$ that recognizes it. Then the machine $M$ will not accept any input larger than both $v$ and $n$. Thus it will recognize only a finite language. Conversely, if both languages are equal, them $M$ recognizes all inputs, hence infinitely many. Thus a pair $(⟨M_1⟩,⟨M_2⟩)$ is in Q iff the language accepted by $M$ is infinite. $\endgroup$
    – babou
    Commented Aug 8, 2015 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.