Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 1 / f

Let $V$ be the decidable language of syntactically valid descriptions $\mathrm{enc}(M)\#\#w$. ThenHere 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. 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. ThenFor the first many-one reduction, use the total computable functionFor 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, useThe 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