Reduction from HALT to MPCP via TM Configuration Transitions


I have book with a very simple reduction from HALT to MPCP and I suspect that it is wrong. Here is the reduction:

Add the following dominos $ (top, bottom$ ):

  • Start: $ (\langle \varepsilon \rangle ,\langle \varepsilon\rangle \langle\kappa_0\rangle)$ for initial configuration $ \kappa_0$ .

  • Step: $ (\langle\kappa_i\rangle, \langle\kappa_j\rangle)$ for all configuration transitions $ \kappa_i \rightarrow \kappa_j$

  • Finish: $ (\langle\kappa_e\rangle \langle\varepsilon\rangle, \langle\varepsilon\rangle)$ for all final configurations $ \kappa_e$

This is much easier than what I see e.g. in Sipser. Is there an error in this proof? I think it is impossible to add a domino for all possible configuration transitions.


You may need the definition of configuration transitions:

Let $ T = (S, \Sigma, \Pi, \delta, s_0, \_, E)$ be a TM. Every triple $ (\nu,s,\omega)$ with $ \nu, \omega \in \Pi^{+}$ and $ s \in S$ is called configuration of $ T$ . The configuration transitions $ \rightarrow_{T}$ is defined as

movement to the right: $ \delta(s,\sigma) = (s’, \sigma’, \rightarrow), \varrho, \sigma \in \Pi$

\begin{align*} (\nu \varrho, s, \sigma \omega) \rightarrow_{T} \left\{\begin{array}{ll}% (\nu \varrho \sigma’ ,s’, \omega) & \mbox{if $ \omega \neq \epsilon$ } \ (\nu \varrho \sigma’ ,s’, \_) & \mbox{if $ \omega = \epsilon$ } \end{array}\right. \end{align*} movement to the left: $ \delta(s, \sigma) = (s’, \sigma’, \leftarrow), \varrho, \sigma \in \Pi$ \begin{align*} (\nu \varrho, s, \sigma \omega) \rightarrow_{T} \left\{\begin{array}{ll}% (\nu, {s’}, \varrho {\sigma’} \omega) & \mbox{if $ \nu \neq \epsilon$ } \ (\_, {s’}, \varrho {\sigma’} \omega) & \mbox{if $ \nu = \epsilon$ } \end{array}\right. \end{align*}