Have a few basic questions about mapping reductions
I have the following statements about mapping reductions of a known
language to another language. I'm trying to understand what each means
relative to the computability classes of languages.
For example, $L_D$ $¡Ü_M$ $L$ implies that $L$ is not in $RE$.
What do each of these imply?
1) $L¡Ü_ML_D$, I"m guessing this implies that $L_D$ is in $RE$?
2) $L¡Ü_M$ {$0^n1^n$ | $n$ ¡Ê N}
3) $A_{TM}¡Ü_ML$ (L with a bar on it, I don't know how to type that)
4) $REGULAR¡Ü_ML$
No comments:
Post a Comment