Is there any uncountable Turing decidable language?

Question

There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?

Answer 1

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.

Answer 2

Every language over a finite (or even countable) alphabet is countable. Assuming your Turing machine alphabet is finite, any language it can possibly accept is countable.

Answer 3

Classical computability discusses functions over finite strings from a finite alphabet. As a result all languages whether decidable or undecidable are countable.

To consider uncountable languages we have to look at infinite strings in place of finite strings. (AFAIK, having an infinite alphabet is not very interesting and doesn't correspond to a realistic model of computation by itself.)

There are models of computation where we can deal with infinite strings which allow us to represent objects from uncountable domains like real numbers. These are often represented as higher-type computations. One model which uses Turing machines is the TTE model. In this model the input can be infinite strings and the machines can access any item in the string it wants. The machine does not need to terminate, however there are conditions to make sure the machine's output converges.

Let's assume that our machine's input is from $\Sigma^\omega$, i.e. infinite strings from alphabet $\Sigma$, e.g. $\Sigma = \{0,1\}$. Then there are $\Sigma^\mathbb{N} = 2^\mathbb{N}$ strings. Therefore there are $2^{2^\mathbb{N}}$ possible languages. The number of TTE Turing machines is still countable. So most of these languages are undecidable.

But there is something even more interesting here: if you want the machine to always halt it will be able to read only a finite initial part of the input. As a result we have the following: Let $M$ be a TTE machines that always halts (in finite time). Then there is a prefix-free language $L \in \Sigma^*$ and Turing machine $N$ such that for any $x\in \Sigma^\omega$, $M$ accepts $x$ iff $N$ accepts the initial part of $x$ which is in $L$.

To put in simple terms, the computaion of TTE Turing machines that always halt is determined by computation of a Turing machine on finite strings.

---

Let me give some example of decidable and undecidable languages of infinite strings:

1. For any $k\in \mathbb{N}$ the language of infinite strings whose $k$th position is 0 is decidable. The same with $k$th position being 1. Intersection of any two decidable languages is decidable, e.g. strings whose $3$th position is 0 and $6$th position is 1.

2. The union of any two decidable languages is decidable. E.g. strings which start with $0$ or $10$.

3. Let $L_i$ be a computably enumerable list of decidable languages. Then $L = \cup_i L_i$ is semi-decidable, i.e. there is machine that halts and accepts whenever a strings in $L$ and does not accept when the strings is not in $L$. If it is not in $L$ the machine might not halt. Any semi-decidable language can be obtains through taking union of an enumerable list of language of the form given in item 1 above.

4. A language is decidable iff both the language and its complement are semi-decidable.

5. The language containing the inifinite strings of 0s is not decidable. This might look strange but look at it this way: when reading the string when can be halt and say the input consists of all 0s? If you stop after reading $k$ 0s your machine will also accept the language which starts with $k$ 0s and follows by all 1s. Note that the only access we have to the string in this model is asking for a bit and getting it.

---

This might make you think that TTE is not an interesting model. But it turns out that computation over infinite strings using TTE model is actually quite interesting. It is based on the intuition that to obtain any finite part of the output you can read only a finite part of the input. In other words, any finite information about the output depends only on finite amount of information about the input. It turns out that functions we are interested in computing follow this rule, otherwise we could not compute them. E.g. consider read numbers encoded as binary strings and the function $x \mapsto \lg x$. We give a finite approximation of the number $x$ to the machine and it returns a finite approximation of the number $\lg x$ to us.

---

Many of these become more intuitive if you know a bit of topology. The essential idea here is that we can define an information topology on strings and with respect to that topology any computable function has to be continues. As a result, when we have a total computable function $f$ whose codomain is $\{0,1\}$ the $f^{-1}(1)$ has to be clopen. Other realistic models of computation over real numbers (not just floating point but really infinite real numbers) have this property. If you are interested a good place to read about TTE is Klaus Weihrauch's book "Computable Analysis". There are also lots of other references on the website for Computability and Complexity in Analysis Network.