2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Have you tried proving there is no such language? $\endgroup$
    – John L.
    Jun 16, 2019 at 13:34

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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, 2019 at 19:30
  • $\begingroup$ That's exactly what I mean. $\endgroup$
    – Yuval Filmus
    Jun 17, 2019 at 19:31
  • $\begingroup$ Ok, I get it. Thank you! $\endgroup$
    – Da Mike
    Jun 17, 2019 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.