-1
$\begingroup$

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.

$\endgroup$

closed as unclear what you're asking by Ran G., Raphael Jun 7 '15 at 21:35

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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
3
$\begingroup$

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.

$\endgroup$
  • $\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.