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
0 comments:
Post a Comment
Let us know your responses and feedback