patternMinor
Can a recursive language be uncountable?
Viewed 0 times
canuncountablerecursivelanguage
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#41963, answer score: 5
Revisions (0)
No revisions yet.