We know that the halting problem $A_{TM}$ and the diagonal language K are mapping reducible to each other. Furthermore both are complete with respect to the mapping reduce relation.

I would like to prove that any r.e. language is mapping reducible to K directly without reducing to $A_{TM}$. How can this be done?


Let $A=L(M)$ be any r.e. language. We reduce $A$ to $K$ using the following reduction function $f(x)$.

Given any word $x$, construct a TM $N_x$ such that, when run on input string $y$, it ignores it, and simulates $M$ on $x$. If $M$ accepts, we make $N_x$ accept, otherwise we make $N_x$ diverge. We let $f(x) = \langle N_x \rangle$.

$f$ is clearly a total computable function. It is also simple to check that $x\in A \iff f(x)\in K$.

Note that $f(x)\in K$ means that the TM encoded by $f(x)$ halts on input $f(x)$. This means that $N_x$ halts on input $y = \langle N_x \rangle$. The value of $y$ is actually irrelevant, since $N_x$ will ignore it, and halt only when $M$ accepts $x$, i.e. when $x\in A$.

In a sense, the "trick" here was to ignore the diagonal property which is used in the definition of $K$, and just make $N_x$ halt on all inputs $y$ or diverge on all inputs $y$. In such way, we surely include the diagonal, and we simplify the reduction function $f$.

If we really wanted, it is possible to define a function $f(x)$ which produces the encoding of $N_x$, which always halts (or always diverges, if we prefer that) on any $y\neq f(x)$, and instead halts on the the diagonal $y=f(x)$ if and only if $x\in A$. Defining such $f$, however, is harder, and requires the second recursion theorem. Ignoring $y$ makes $f$ much simpler to construct.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.