# Explain why if the language A is recursive, then A is reducible to 0*1*

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.
@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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7477357983589172, "perplexity": 142.21987757118148}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-06/segments/1422115858583.14/warc/CC-MAIN-20150124161058-00038-ip-10-180-212-252.ec2.internal.warc.gz"}