= Solution
Let $V$ be the <decidable language> of syntactically valid descriptions $\operatorname{enc}(M)\#\#w$. Then
$$
\mathcal L_{\mathrm H}\mathbin{\dot\cup}\mathcal L_{\mathrm{NH}}=V,
\qquad
\overline{\mathcal L_{\mathrm H}}
=\mathcal L_{\mathrm{NH}}\mathbin{\dot\cup}(\Sigma^*\setminus V).
$$
Here the <complement of a set> on the left is taken in all <words over an alphabet>, while the non-halting problem only has valid machine-and-input descriptions as instances. \b[Any malformed description belongs to $\overline{\mathcal L_{\mathrm H}}$ but not to $\mathcal L_{\mathrm{NH}}$.] For example, the <empty word> has no separating `##`, so cannot be a valid instance under the displayed encoding.
Fix valid descriptions $h$ and $\ell$ of, respectively, an immediately halting <Turing machine> on the <empty word> and a <Turing machine> looping forever on the <empty word>. Then
$$
h\in\mathcal L_{\mathrm H},\qquad
\ell\in\mathcal L_{\mathrm{NH}}.
$$
For the first <many-one reduction>, use the total <computable function>
$$
f(x)=
\begin{cases}
x,&x\in V,\\
\ell,&x\notin V.
\end{cases}
$$
For a valid <input>, nonmembership in $\mathcal L_{\mathrm H}$ is exactly membership in $\mathcal L_{\mathrm{NH}}$, so retaining it is correct. Every invalid <input> is a yes-instance of $\overline{\mathcal L_{\mathrm H}}$, and $f$ sends it to the fixed yes-instance $\ell$. Therefore $x\in\overline{\mathcal L_{\mathrm H}}$ if and only if $f(x)\in\mathcal L_{\mathrm{NH}}$.
For the reverse <many-one reduction>, use
$$
g(x)=
\begin{cases}
x,&x\in V,\\
h,&x\notin V.
\end{cases}
$$
The equivalence again holds on valid <inputs>. Invalid <inputs> are no-instances of $\mathcal L_{\mathrm{NH}}$, and $h$ is a no-instance of $\overline{\mathcal L_{\mathrm H}}$. Syntax checking terminates, so $g$ is also a total <computable function>. We have proved
$$
\boxed{\overline{\mathcal L_{\mathrm H}}\leq_m\mathcal L_{\mathrm{NH}}
\quad\text{and}\quad
\mathcal L_{\mathrm{NH}}\leq_m\overline{\mathcal L_{\mathrm H}}.}
$$
Back to article page
