# How do we show that the polynomial time reduction of one problem to another has been done in polynomial time?

I have just been reading through a SO post which proves that the Halting Problem is NP-Hard. Whilst this is an easily followed proof, one slight slight aspect of it has left me scratching my head: it says that

"This pairing can be done in polynomial time, because the Turing machine has only constant size."

So their justification for saying that the reduction was done in polynomial time is that the Turing machine 'only has constant size'.

Why would this prove that the reduction was done in polynomial time?

$$\varphi\mapsto \big(\langle M\rangle,\varphi \big)$$
where $\varphi$ is a CNF formula and $M$ is the Turing machine which given a CNF $\psi$ as input, iterates over all the possible assignments to the variables of $\psi$, and enters a loop iff no satisfying assignment was found.
The machine $M$ does not depend on the input of the reduction, so it has some constant size description independent of the input $\varphi$. This means that you can output $\langle M \rangle$ in polynomial (even constant) time relative to the size of $\varphi$, hence the reduction is computable in polynomial time.
Note that you only need to show that you can generate $\langle M \rangle$ in polynomial time, which does not necessarily mean it has to have a constant size. Suppose e.g. that we want to show that $L=\{\langle M\rangle | \text{M halts on input$\epsilon$}\}$ is NP hard. In that case, the reduction $\varphi\mapsto \langle M_{\varphi}\rangle$ does the trick, where $M_{\varphi}$ is the machine which ignores its input, iterates over all possible assignments for $\varphi$, and enters a loop if no satisfying assignment was found. $M_{\varphi}$ does not have a constant size description, since you have to hardcode $\varphi$ into it. However, you can still generate $\langle M_{\varphi}\rangle$ in polynomial time, which makes the reduction polynomial.