Does there exist a recursive language $L$ whose cardinality is uncountable?
I would like to have an explanation whether Turing Machine can encode uncountable languages and whether we can use this to reject the initial question.
$\begingroup$
$\endgroup$
3
asked Apr 29, 2015 at 17:00
-
1$\begingroup$ Over finite words and a finite alphabet $\Sigma$, every language is countable, since $\Sigma^*$ is countable... $\endgroup$– ShaullCommented Apr 29, 2015 at 17:12
-
$\begingroup$ so you are saying there is no uncountable language that is recursive? $\endgroup$– revisingcomplexityCommented Apr 29, 2015 at 17:27
-
1$\begingroup$ Yes. To be uncountable is, literally, a big deal. $\endgroup$– André Souza LemosCommented Apr 29, 2015 at 17:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
Languages are collections of words. Words are finite strings.
As Shaull stated in his comment, every language over a finite alphabet is countable. (In fact, every language over a countable alphabet is also countable.)
Languages of infinite words, sometimes called $\omega$-languages, are considered in computer science. For example, they are the subject of $\omega$-automata theory. But the Turing machine formalism is about the usual notion of language.
-
$\begingroup$ How do we prove this though? $\endgroup$ Commented Apr 29, 2015 at 17:50
-
$\begingroup$ what about the language that halts if the first number in a binary number is a 1? $\endgroup$ Commented Apr 29, 2015 at 17:59
-
$\begingroup$ @revisingcomplexity Shauli gives the proof, assuming that you accept that $|A| \leq |B|$ if $A \subseteq B$. $\endgroup$– RaphaelCommented Apr 29, 2015 at 18:02
-
2$\begingroup$ Languages are collections of words. Words are finite strings. The input is always finite. That's how languages are defined in the context of computability. Deal with it. $\endgroup$ Commented Apr 29, 2015 at 18:11
-
1$\begingroup$ @YuvalFilmus, That was the biggest gap in our knowledge that made us misunderstood most of the concept. Me and other students revising together are really, thankful for your explanation. THANK YOU! $\endgroup$ Commented Apr 29, 2015 at 18:17