Reduction of A_LBA to E_LBA

Question

I have a rather interesting one to ponder and would love if I could get an answer for it. We were discussing the topic of mapping reduction today in my Computing theory course and I was wondering why this reduction can't exist, $A_{LBA} \leq_{m} E_{LBA}$, since both of them are linear bound automata (LBAs). I do realize that $E_{LBA}$ is undecidable, $A_{LBA}$ is decidable, and the normal proof uses $A_{TM}$, or $E_{TM}$, to prove the undecidibility of $E_{LBA}$. I am just curious why the proof is using a TM to prove an LBA. But, my Professor could not come up with a solution to my confusion. I was wondering is this possible, if so, why or why not.

Definitions:

$A_{LBA} = \{\langle M, w\rangle \mid \text{$M$ is a linear bound automaton that accepts the string $w$}\}$

$E_{LBA} = \{\langle M \rangle \mid \text{$M$ is a linear bound automaton with $L(M)=\emptyset$}\}$

$A_{TM}$ and $E_{TM}$ are the equivalent problems for Turing Machines.

Answer 1

You have your mapping the wrong way around. As it stands, it would be a reduction from a decidable problem to an undecidable problem. It's certainly possible (see below), but it doesn't tell us anything.

Recall that if $A \leq_{m} B$, then an algorithm solving $B$ (or deciding membership in this case) can be used to solve $A$ (decide membership in $A$). So the reduction you're looking at would tell us that any decider for $E_{LBA}$ could be used to decide $A_{LBA}$. We happen to also know that $E_{LBA}$ is undecidable, but this doesn't prevent there being some decider for $A_{LBA}$ that doesn't decide $E_{LBA}$.

In fact, the reduction that can't exist is $E_{LBA} \leq_{m} A_{LBA}$, as this would imply that we could decide $E_{LBA}$, which we know we can't.

For the second part, the proof (or rather, one of the possible proofs) that $E_{LBA}$ is undecidable is via constructing the mapping $A_{TM} \leq_{m} E_{LBA}$, so again a decider for $E_{LBA}$ would give us a decider for $A_{TM}$, but we already know that $A_{TM}$ is undecidable so $E_{LBA}$ must also be undecidable.

As to why the proof uses a language that involves Turing Machines to show something about linear bound automata, it's because it works.

A Reduction

As $A_{LBA}$ is decidable, we can take the input LBA $M$ and string $w$, and run the decider on $\langle M, w\rangle$. If it accepts, we map this to an LBA $M_{rej}$ that immediately rejects. If the decider rejects, we map it to an LBA $M_{acc}$ that immediately accepts. Thus $M_{acc}$ accepts all input and is not in $E_{LBA}$, and $M_{rej}$ rejects all input and is in $E_{LBA}$.

Note of course that this reduction is in a sense trivial, and the subset of $E_{LBA}$ it maps to is finite and therefore decidable (even regular!).

Another Perspective

Given two languages $A$ and $B$ such that $A \leq_{m} B$, there's two basic (useful) things we might be able to say:

• If $B$ is decidable then $A$ is also decidable.
• If $A$ is undecidable then $B$ is also undecidable.

In our case $A$ is decidable, and $B$ is undecidable, which matches neither of these possibilities, so the reduction $A_{LBA}\leq_{m}E_{LBA}$ doesn't tell us anything about the decidability of either.