4
$\begingroup$

Let $A$ and $B$ be two languages. If $A \le_{m} B$ ( reducible by mapping ) then I know that if $B$ is decidable so is $A$ and if $B$ is recognizable so is $A$. And if $A \le_{T} B$, then if $B$ is decidable so is $A$. But I can't say the same thing for recognizability which I can see by example when $A \equiv L_{\phi}$ ( the empty language ) and if $B \equiv A_{TM}$ ( acceptance language ). I know this is because of the fact that we assume the orcale to decide $B$ while proving $A \le_{T} B$. Why is it so that we assume the oracle to decide and not recognize $B$ while comparing relative difficulty of two two languages ? Sorry for vague terminology of relative difficulty, I have not yet begun reading about complexity theory and hierarchies and for now only have a vague idea about it.

$\endgroup$
2
$\begingroup$

You can define a notion of reducibility which will ensure that if $A$ reduces to $B$ and $B$ is recognizable then so is $A$. The definition allows an oracle call to $B$, but the semantics are different: if the contents of the oracle tape are in $B$ then the machine continues, and otherwise it gets stuck (never halts).

The problem with this definition is that it is pretty weak. While the other property (with recognizability replaced by decidability) still holds, it never helps you that $B$ is decidable. Compare this with mapping reducibility: there you are using the full power of decidability.

Still, the definition could be useful. Assuming you aren't the first to come up with this idea, the only conclusion is that this definition doesn't lead to a nice enough theory. It's also possible that you came up with a nice concept which you could develop to a nice theory. A third possibility is that a theory has been developed, but I am unaware of it.

$\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.