Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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 having trouble with this question:

Given any language L is a subset of $\{0,1\}^*$, define the language

$$\text{unary}(L) =\{0^{1x} | x \in L\}$$

The language $\text{unary}(L)$ is said to be unary since it is a subset of $ 0^*$. Show that $L$ is recursive if and only if $\text{unary}(L)$ is recursive.

share|cite|improve this question

Suppose $L$ is recursive; then there is a TM $M_L$ that recognizes $L$. Then a TM to accept $\text{unary}(L)$ is as follows: First it reads in the string of zeroes, incrementing a binary counter on an auxiliary tape for each zero it reads (and rejecting if the input string is not all zeroes). When it finishes counting the zeroes, it simulates $M_L$ on the binary numeral that is on the auxiliary tape.

To prove the opposite direction, do the opposite: Given a string in $\{0,1\}^*$, it represents a binary numeral. Decrement this numeral repeatedly and write a 0 on the auxiliary tape for each decrement, until the numeral reaches 0. Then simulate $M_{\text{unary}(L)}$ on the string of zeroes.

share|cite|improve this answer

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.