2
$\begingroup$

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.

1 Answers 1

2

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.