As explained in answers to this question, reduction from $A \le B$ can be represented in the following way. enter image description here

But in this example: enter image description here from here

At least as I understand it: The reduction is from $\overline{HP}$ to $L_2$, so $A$ is $\overline{HP}$ and $B$ is $L_2$. But it's implemented in the way that $M'$ is TM of $L_2$ and $M$ is TM of $\overline{HP}$, and $M'$ execute $M$ (I mean $L_2$ is the external and $\overline{HP}$ is the internal).

Where am I wrong?


What confuses you is that the words in the languages are encodings of machines that simulate runs of other machines, but at the end of the day, these are just words. Specifically, given input $x = \langle M, x\rangle$ for the reduction, the reduction itself does not simulate the run of $M$ on $x$, the reduction only outputs $f(x) = \langle M'\rangle$ which is an encoding of a machine. The machine $M'$, by definition, simulates the run of $M$ on $x$, given any input $w$ for $M'$. You can think of this reduction as a python code $f$ that is given as input another python code $M$ and an input $x$ for $M$. Then, $f$ halts and outputs a python code $M'$. Note that $M'$ may never halt on any input $w$, but this is okay as $f$ never runs $M'$.

Please note that the first attached figure is irrelevant here as it does not describe how the reduction operates (how $M_f$ computes $f(x)$, given $x$), it only describes how you can define a machine $M_A$ for $\overline{HP}$ assuming that you already have: 1) a machine $M_B$ for $L_2$, and 2) a machine $M_f$ that computes the reduction $f$.

  • $\begingroup$ Thank you! I read it couple of times and should think about it, I'm not sure I got it $\endgroup$ – ChaosPredictor Jan 16 at 16:43
  • 1
    $\begingroup$ You're welcome. Yes, it could be confusing if you see it for the first time. $\endgroup$ – Bader Abu Radi Jan 16 at 17:40

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.