1
$\begingroup$

What happens if I build the following mapping function from $A_{\mathrm{TM}}$ to $A_{\mathrm{LBA}}$ (LBA means linear TM with a limited tape space and $A_{\mathrm{LBA}}$ is decidable):

If $M$ accepts $w$ then returns an LBA which decides the language {'111'}.

Clearly if $(M,w)$ is in $A_{\mathrm{TM}}$ then $f(M,w)$ is in $A_{\mathrm{LBA}}$ but then $A_{\mathrm{TM}}$ would be decidable!

What am I missing here?

$\endgroup$
  • 1
    $\begingroup$ If M accepts w is what you cannot implement using a Turing machine that always halts. $\endgroup$ – Yuval Filmus Apr 14 '18 at 20:38
  • $\begingroup$ Did you mean then if F(w) is in A_LBA then i can decide it while i can't decide if the same w is in ATM, therefore breaking the if-and-only-if condition of the reduction ? $\endgroup$ – Caffeine Apr 15 '18 at 0:26
2
$\begingroup$

... but then $A_{\mathrm{TM}}$ would be decidable!

No. Because your $f$ is not computable since one cannot compute whether $M$ accepts $w$, as Yuval Filmus said in the comment.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

If a language $B$ is decidable, there is an algorithm that computes it. If a language $A$ is mapping-reducible to $B$, then you have the following algorithm for $A$: first compute the translation given by the mapping reduction; then use the algorithm for $B$.

So, if $A$ has a mapping reduction to some decidable language, then $A$ must also be decidable. OK, I don't think I've yet told you anything you don't know. We can conclude that either the halting problem is decidable, or the halting problem for LBAs is undecidable or the thing that you're calling a mapping reduction isn't actually a mapping reduction.

It's the third option. A mapping reduction from $A$ to $B$ is a computable function $f\colon\Sigma^*\to\Sigma^*$ such that $x\in A$ if, and only if, $f(x)\in B$. Well, first things first, you haven't actually defined a function from $\Sigma^*$ to $\Sigma^*$: you've only defined a function from $A_\mathrm{TM}$ to $\Sigma^*$. Specifically, you've not said what $f(x)$ is when $x\notin A_\mathrm{TM}$.

So, suppose we extend your definition to be $$f(\langle M,w\rangle)=\begin{cases}\langle A,111\rangle&\text{if $M(w)$ halts}\\ \langle A,000\rangle&\text{if $M(w)$ does not halt,} \end{cases}$$ where $A$ is some LBA that accepts the langauge $\{111\}$.

This function $f$ certainly has the $x\in A\Leftrightarrow f(x)\in B$ property but it's not computable, so it doesn't define a mapping reduction. In particular, you'd have to solve the halting problem to compute it, since it's of the form, “If the input halts, do $X$; else, do $Y$.” If you could compute $f$, you'd already be able to solve the halting problem, so you wouldn't need to use the reduction!

| cite | improve this answer | |
$\endgroup$

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.