patternMinor
Undecidability and Countability
Viewed 0 times
andcountabilityundecidability
Problem
This question is prompted by Undecidable unary languages (also known as Tally languages)
How does the countability of a language imply (un)decidability?
How does the countability of a language imply (un)decidability?
Solution
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.
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.
Context
StackExchange Computer Science Q#21609, answer score: 6
Revisions (0)
No revisions yet.