# Can such a Turing-recognizable language exist?

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.

• Have you tried proving there is no such language? Jun 16, 2019 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.