3
$\begingroup$

This question is prompted by Undecidable unary languages (also known as Tally languages)

How does the countability of a language imply (un)decidability?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Countability doesn't imply (un)decidability: the set of even numbers and the set of codings of Turing machines that halt on input zero are both countable but the first is decidable and the second isn't.

Conversely, for any finite alphabet $\Sigma$, the set $\Sigma^*$ of all finite strings over $\Sigma$ is countable, since each string can be seen as a natural number written in base $|\Sigma|$. Therefore, any language (i.e., any subset of $\Sigma^*$) is also countable.

The only place that uncountability comes in is that there are uncountably many different languages over any finite $\Sigma$. This gives an immediate proof of the existence of undecidable languages: there are uncountably many languages but only countably many Turing machines.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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