Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
1  
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. – Marc van Leeuwen Feb 16 at 14:24
up vote 17 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
1  
Why would the alphabet need to be countable? – leftaroundabout Feb 16 at 14:04
2  
Every model being studied has finite alphabet. If the alphabet also becomes infinite (countable or uncountable) it is difficult to have a reasonable model. – Shreesh Feb 16 at 14:53
    
@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? – Yakk Feb 16 at 15:24
1  
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. – Shreesh Feb 16 at 16:03
    
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. – Owen Feb 16 at 20:10

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.

share|cite|improve this answer
1  
"As a result all languages are finite" - Do you mean countable? – Anton Trunov Feb 19 at 8:38
    
I think so Mr. Trunov. – Jyotirmoy Pramanik Feb 19 at 9:13
    
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? – Raphael Feb 19 at 9:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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