0
$\begingroup$

Let S be a subset of N (natural numbers), so it is infinite and countable. Let Ls={a^n | n belongs to S} a language. Is Ls recursive? Is Ls recursively enumerable? Justify your answers.

I'm pretty sure that Ls is recursive for any S, because we can write a program that decides Ls (or a Turing Machine for that matter). But how do I justify it?

$\endgroup$
0
$\begingroup$

We have $a^n\in L$ if and only if $n\in S$. Take the set $K=\{n\mid n\in{\rm dom}\,\phi_n\}$, where $(\phi_n)$ is the sequence of unary part. rec. functions. The set $K$ is undecidable. So if you take $K=S$, then $L$ is undecidable too. But $K$ re., not recursive since its complement is not re. Take $S=\overline K$. Then $L$ is not re.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.