I'm in a theory of computation class and there is a problem that I think I am way overthinking.
Can anyone point me in the right direction with the following: Give a short justification of the fact that if the language A is recursive, then A ≤m 0*1* (A is mapping reducible to the language 0*1*).
I know that if A is recursive it means there is a Turing Machine that accepts it that will halt for every input. The language 0*1* is includes strings with any number of zeroes followed by any number of ones. What I can't see is how to get a function that will reduce any input for any recursive language into an input for 0*1* so that A accepts iff 0*1* accepts.
I already easily answered several other questions that were together with this and they all had one or two sentence simple explanations, but my mind is just drawing blanks with this one. Any ideas would be greatly appreciated!
Choose $w_0 \not\in 0^* 1^*$ and $w_1 \in 0^* 1^*$, e.g. $w_0 = 10$ and $w_1 = 0$. Then $$f(x) = \begin{cases}w_0 \text{ if } x \not\in A,\\ w_1 \text{ if } x \in A\end{cases}$$ is a computable function that reduces $A$ to $0^* 1^*$. The computability follows from $A$ being recursive.