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$
1
-
$\begingroup$ What does it mean for a Turing machine to "generate" a language? Turing machines normally accept or decide languages. $\endgroup$– David RicherbyDec 17, 2014 at 8:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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, 2014 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$ Dec 18, 2014 at 7:51
-
1$\begingroup$ Right. But in this context the alphabet is always assumed to be finite. $\endgroup$ Dec 18, 2014 at 8:16