17
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If the language of all possible words is uncountable (which requires an uncountable alphabet) then it immediately provides an example of a (trivially) Turing decidable uncountable language. If it is not (i.e., it is countable), then sublanguages are not uncountable either. $\endgroup$ – Marc van Leeuwen Feb 16 '16 at 14:24
24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What about set of all languages of finite number of strings over countably infinite alphabet? Is it countable or uncountable? Also I was not able to think of proof for "language over countably infinite alphabet is countable". $\endgroup$ – anir 2 days ago
  • $\begingroup$ Your set is also countable. $\endgroup$ – Yuval Filmus 2 days ago
  • $\begingroup$ This proves "set of languages over finite alphabet is countable". I feel we can prove "set of languages containing countably infinite strings over finite alphabet is countable" following same proof approach due to finite alphabet. But I am unable to imagine how this approach can be adapted for countably infinite alphabet. $\endgroup$ – anir 2 days ago
  • $\begingroup$ You cannot prove it since it’s false. The number of infinite binary sequences is already uncountable. $\endgroup$ – Yuval Filmus 2 days ago
11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why would the alphabet need to be countable? $\endgroup$ – leftaroundabout Feb 16 '16 at 14:04
  • 2
    $\begingroup$ Every model being studied has finite alphabet. If the alphabet also becomes infinite (countable or uncountable) it is difficult to have a reasonable model. $\endgroup$ – Shreesh Feb 16 '16 at 14:53
  • $\begingroup$ @Shreesh Well, if the alphabet is uncountable, a naive mapping of a FSM (with uncountable transitions between a finite number of states) might be rather powerful? $\endgroup$ – Yakk Feb 16 '16 at 15:24
  • 1
    $\begingroup$ True, these are the kind of extensions, which might have language classes which might be superclass of RE or recursive languages. But they are not studied well, if studied at all. Biggest problem is, in my opinion, how can we give a finite representation of the machine. Then you have to write the symbol in a tape cell. Even the humble cell may need infinite memory to store the description of the tape symbol being written. $\endgroup$ – Shreesh Feb 16 '16 at 16:03
  • $\begingroup$ This is a great explanation. I would add that even if a usual accept/reject criterion is used, you could sort of say there still exist some languages that a Turing machine could decide and would technically have uncountably many strings, but only because the vast majority of the characters are "useless" to the language. $\endgroup$ – Owen Feb 16 '16 at 20:10
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "As a result all languages are finite" - Do you mean countable? $\endgroup$ – Anton Trunov Feb 19 '16 at 8:38
  • $\begingroup$ I think so Mr. Trunov. $\endgroup$ – Jyotirmoy Pramanik Feb 19 '16 at 9:13
  • $\begingroup$ This is a nice post but I fail to see what its bulk has to do with the specific question asked here. Maybe you wanted to create a question-answer-pair? $\endgroup$ – Raphael Feb 19 '16 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.