Suppose $\Sigma = \{a,b\}$. Is the following claim correct?

There exists a Turing-recognizable language $L \subseteq \Sigma^*$ such as its complement is not Turing-recognizable, and for all $n \in \mathbb{N}$ it contains exactly $n$ strings of length $n$.

I'm kind of lost here. Any help would be appreciated.

  • 1
    $\begingroup$ Have you tried proving there is no such language? $\endgroup$ – John L. Jun 16 '19 at 13:34

If $L$ is a recognizable language that contains $f(n)$ strings of length $n$, where $f$ is computable, then $L$ is in fact computable. Given a string $x$ of length $n$, calculate $f(n)$, and then run a recognizer for $L$ on all strings of length $n$. Eventually you will find all $f(n)$ strings recognized by $L$. If $x$ is one of them, accept, and otherwise, reject.

  • $\begingroup$ When you say "then run a recognizer for L on all strings of length n" you mean in parallel for every string of length n? $\endgroup$ – Da Mike Jun 17 '19 at 19:30
  • $\begingroup$ That's exactly what I mean. $\endgroup$ – Yuval Filmus Jun 17 '19 at 19:31
  • $\begingroup$ Ok, I get it. Thank you! $\endgroup$ – Da Mike Jun 17 '19 at 21:30

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.