Are all languages generate by Turing machines countable? I know that the set of all TMs are countable, but what about the languages that they generate?
$\begingroup$
$\endgroup$
-
$\begingroup$ What does it mean for a Turing machine to "generate" a language? Turing machines normally accept or decide languages. $\endgroup$ – David Richerby Dec 17 '14 at 8:29
$\begingroup$
$\endgroup$
Yes. All languages, not only those generated by Turing machines, are countable. This is because they are all subsets of $\Sigma^*$, and $\Sigma^*$ itself is countable. However, there are uncountably many languages.
answered Dec 17 '14 at 6:34
-
1$\begingroup$ Not all languages are countable e.g. for language of first order logic one sometimes add constants denoting every element. If such language describes real nunbers then such language is uncountable. $\endgroup$ – Trismegistos Dec 18 '14 at 7:51
-
1$\begingroup$ Right. But in this context the alphabet is always assumed to be finite. $\endgroup$ – Yuval Filmus Dec 18 '14 at 8:16
