I am trying to see if infinite languages are always decidable. I believe it is not always decidable because there will not be a maximum length of string for the Turing machine to halt. Am I on the right path? I am having difficulty coming up with an example infinite language That is decidable.

  • $\begingroup$ Are these languages with an infinite number of words? With words that may have infinite length? Both? $\endgroup$ – André Souza Lemos May 8 '15 at 19:15
  • $\begingroup$ Finite set of strings in the language $\endgroup$ – Jake May 8 '15 at 19:33
  • 1
    $\begingroup$ I suggest that you edit the question, making this distinction explicit. It is not an easy guess. $\endgroup$ – André Souza Lemos May 8 '15 at 20:03
  • $\begingroup$ All finite languages are regular and thus decidable. Some of the infinite languages are decidable and some are not. See cs.stackexchange.com/a/11289 $\endgroup$ – Ran G. Jun 7 '15 at 21:00
  • $\begingroup$ and see also cs.stackexchange.com/questions/1990 $\endgroup$ – Ran G. Jun 7 '15 at 21:03

There are many infinite languages which are decidable, for example $\Sigma^*$, or the language of all (binary representations of) primes. However, in some sense "most" languages are undecidable, since there are uncountably many languages, but only countably many decidable languages. We also know many explicit undecidable languages, such as the language of (encodings of) Turing machines which halt on the empty input.

All finite languages, on the other hand, are decidable.

| cite | improve this answer | |
  • $\begingroup$ So you are saying the complement of a finite language is decidable? $\endgroup$ – Jake May 8 '15 at 20:47
  • $\begingroup$ I wasn't saying that, but that's definitely true. $\endgroup$ – Yuval Filmus May 8 '15 at 20:47
  • $\begingroup$ Oh ok thank you. Also you say in your answer all finite languages are decidable could you elaborate a little further on that? $\endgroup$ – Jake May 8 '15 at 21:10
  • $\begingroup$ Yes. All finite languages are decidable. Make sure that you understand what decidable means. Give it a few hours before asking any more questions here - I'm sure you'll get it by then. $\endgroup$ – Yuval Filmus May 8 '15 at 21:12
  • $\begingroup$ @Jake Think about how you'd write a computer program that checks if a word is in a specified finite language. It doesn't have to be a smart program; it doesn't have to be efficient. Once you've convinced yourself that there's a computer program that can do that, you've convinced yourself that the problem is decidable. $\endgroup$ – David Richerby May 9 '15 at 10:09

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