Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Nov 6 '12 at 16:04

This question came from our site for theoretical computer scientists and researchers in related fields.

add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you for correcting me on my mapping and I understand why it's that way. So, if I understand correctly, what your saying in the last section is there is a possibility that $E_{LBA}$ can be worked out to be decidable using that mapping you corrected me on but that it's so trivial who would actually use it? But the more accepted method is the first one using $A_{TM}$? In other words $E_{LBA}$ can be both decidable and undecidable depending on the mapping you use? –  Kevin Stadler Nov 6 '12 at 9:38
    
No, $E_{LBA}$ is definitely undecidable, the last bit is just to show that there is a mapping from $A_{LBA}$ to $E_{LBA}$, but that it doesn't tell us anything interesting. I'll add a little bit to the end to add another perspective. –  Luke Mathieson Nov 6 '12 at 9:41
    
So, then a mapping can exist between some but that mapping doesn't necessarily prove decidability. That's the sticking point for me.Thanks for all the help. –  Kevin Stadler Nov 6 '12 at 17:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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