# Proving iff statement with reductions

I have a statement I am trying to prove, and I'm very close, but I think I'm missing a couple of key concepts about regular and context-free languages.

Question: Let $A = \{ ww \ | \ w \ \epsilon \ \Sigma^{*} \}$.

Show that any language $L$ is Turing-decidable if and only if $L$ is many-one reducible to $A$.

Where I am so far:

1. Language $A$ is not context-free, but the complement of $A$ is context-free.

2. Both $A$ and the complement of $A$ are decidable.

So, that means I can prove one direction of the iff statement fairly easily:

If $L$ is many-one reducible to $A$ then since $A$ is decidable from statement (2) above, also $L$ is decidable.

The other direction is giving me problems. This is all I have gleaned so far:

If $L$ is Turing-decidable, then $L$ is a regular language.

Is there some relation between regular and context-free languages with respect to reductions that I am missing? Or should I be making a different logic jump in this part of the proof?

-
A very minor nit. Instead of \epsilon in your question, use \in to indicate set membership. – Rick Decker Feb 7 '14 at 3:44

## 2 Answers

There is a more general theorem which says that if $A$ is a decidable language and $B$ is a decidable language that is not trivial (in the sense that $B\ne\Sigma^*$ and $B\ne\emptyset\,$), then $A\le_m B$. Roughly speaking, this says that all non-trivial decidable languages are many-to-one reducible to each other, meaning that $\le_m$ is too coarse a metric to distinguish between decidable languges.

In your problem, suppose that $L\subseteq \Gamma^*$ and define a mapping $f:\Gamma^*\rightarrow\Sigma^*$ defined by: $$f(x) = \begin{cases} \mathtt{aa} & \text{if x\in L}\\ \mathtt{a} & \text{if x\notin L} \end{cases}$$ for some $\mathtt{a}\in\Sigma^*$. This is a total computable function (since by definition, we can use the computable decider program to determine $x$'s membership in $L\,$) and it's easy to verify that $x\in L$ iff $f(x)\in A$, which is all you need to show $L\le_m A$. As Yuval noted, you don't need any results about regular or context-free languages to answer this question.

-

First of all, not every decidable language is regular. For example, $A$ is decidable but not regular.

Here is a hint: this question doesn't have anything to do with either regular languages or context-free languages. While we certainly need $A$ to be decidable, for the other direction we only need some really simple properties of $A$. Try to think for which $A$ it is not true that if $L$ is decidable then $L$ can be many-one reduced to $A$.

-
I'm confused, in the direction "if L is decidable...", there isn't any connection from L to A. How can A have any affect on whether or not L is decidable? – Alex Chumbley Feb 7 '14 at 1:30
Why should it have any effect? My question was for which languages $A$ the following statement holds: If $L$ is decidable then it is many-one reducible to $A$. (If, not iff!) – Yuval Filmus Feb 7 '14 at 1:38
Well, L must be "easier" than A since it's L <= A, so A could be decidable or undecidable, really – Alex Chumbley Feb 7 '14 at 1:43