0
$\begingroup$

Consider the reduction $A_{TM} \le_m \overline{E}_{TM}$, where

$$A_{TM} = \{\langle M, w \rangle \mid \text{TM $M$ accepts $w$}\}\text{, and}$$

$$\overline{E}_{TM} = \{\langle M \rangle \mid \text{TM $M$ accepts some string}\}$$

Then define the mapping reduction, $f(\langle M, w \rangle)$ as follows:

Construct a new TM $M^\prime$ that on input $x$

  • rejects if $x \ne w$;
  • otherwise, runs $M(w)$ and accepts if it accepts.

Finally, it outputs $\langle M^\prime \rangle$. This construction ensures that $\langle M, w \rangle \in A_{TM} \Leftrightarrow \langle M^\prime \rangle \in \overline{E}_{TM}$.

Question. The idea makes sense, except that I am having a hard time wrapping my head around infinite loops and the computability of mapping reductions. In particular, what ensures that we can indeed write $\langle M^\prime \rangle$ even if $M$ does not halt on $w$? It seems like the answer should be obvious — that there is some generic way to encode $\langle M^\prime \rangle$, but I don't know how.

Secondly, is it correct to say that $f$ is computable because it is fully determined by its inputs?

$\endgroup$
1
  • $\begingroup$ Please ask only one question per post. $\endgroup$
    – D.W.
    Sep 24 at 5:20

1 Answer 1

2
$\begingroup$

"fully determined by its inputs" does not imply "computable". The halting function is fully determined by its inputs, but not computable.

$\endgroup$
1
  • $\begingroup$ Then (I think) both my questions are really asking the same thing. $\endgroup$
    – ope
    Sep 24 at 5:39

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.