Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.