Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
As explained in answers to this question, reduction from $A \le B$ can be represented in the following way.
But in this example:
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$.
