Problem Detail: 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.
Asked By : revisingcomplexity
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41963
