Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
Thanks, that makes sense and is way simpler than the crazy things my mind was trying to come up with! – scae Jan 31 '13 at 20:54
@Rick Decker: If there is no $x \in A$ then $f(x) = w_0$ for all $x$ which is still a reduction of $A$ to $0^* 1^*$. – marlu Feb 1 '13 at 11:01
I had reversed the roles of $A$ and $0^*1^*$. Now that I've passed that brain stone, you, of course, are correct. – Rick Decker Feb 1 '13 at 13:12

Your Answer


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.