patternModerate
Is there any uncountable Turing decidable language?
Viewed 0 times
anylanguagedecidableturingthereuncountable
Problem
There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?
Solution
We can have uncountable languages only if we allow words of infinite length, see for example Omega-regular language. These languages are called $\omega$-languages. Another example will be language of subset of reals which contains, say, decimal expansions of all real numbers.
There are some models in which Turing Machines are modified to accept $\omega$-languages. Some of these model use Buchi condition for acceptance. Since you cannot see whole of the input in finite time, we say the input is accepted if the Turing Machine enters the accept state infinitely many times. If we can prove this by analyzing the input (not by running it), we say that the input is accepted.
There are some models in which Turing Machines are modified to accept $\omega$-languages. Some of these model use Buchi condition for acceptance. Since you cannot see whole of the input in finite time, we say the input is accepted if the Turing Machine enters the accept state infinitely many times. If we can prove this by analyzing the input (not by running it), we say that the input is accepted.
Context
StackExchange Computer Science Q#53187, answer score: 16
Revisions (0)
No revisions yet.