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.

  • 1
    $\begingroup$ Over finite words and a finite alphabet $\Sigma$, every language is countable, since $\Sigma^*$ is countable... $\endgroup$
    – Shaull
    Apr 29 '15 at 17:12
  • $\begingroup$ so you are saying there is no uncountable language that is recursive? $\endgroup$ Apr 29 '15 at 17:27
  • 1
    $\begingroup$ Yes. To be uncountable is, literally, a big deal. $\endgroup$ Apr 29 '15 at 17:38

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$ Apr 29 '15 at 17:50
  • $\begingroup$ what about the language that halts if the first number in a binary number is a 1? $\endgroup$ Apr 29 '15 at 17:59
  • $\begingroup$ @revisingcomplexity Shauli gives the proof, assuming that you accept that $|A| \leq |B|$ if $A \subseteq B$. $\endgroup$
    – Raphael
    Apr 29 '15 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$ Apr 29 '15 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$ Apr 29 '15 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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