What is the easiest and the most straightforward way to find whether a given language is decidable?

For example, how do we know if the following languages are decidable or not?

`Binary representation of all prime numbers`
`{ empty string(eps) }`
  • 3
    $\begingroup$ If you can write a program that decides the language, then it's decidable. This captures your two examples. $\endgroup$ May 6 '18 at 22:03
  • $\begingroup$ @YuvalFilmus How are they decidable? Can you explain plz? $\endgroup$
    – Dawn17
    May 6 '18 at 22:55
  • $\begingroup$ See How to tell if a language is recognizable, co-recognizable or decidable? $\endgroup$ May 7 '18 at 11:05
  • $\begingroup$ There isn't really an "easiest or most straightforward way". Any mathematical proof is a creative act: it's not a mechanized process where you can just apply some technique, turn the handle and a proof drops out. $\endgroup$ May 7 '18 at 12:12

A language $L$ is decidable if there is an algorithm that halts on every input, says Yes if the input belongs to $L$, and says No if the input doesn't belong to $L$.

The language of all binary representations of prime numbers is decidable since there is an algorithm that decides whether an integer is prime. You can probably code such an algorithm yourself in your favorite programming language. There are a few added complications - you need to parse the input, and you need to handle arbitrarily large integers - but intuitively these are not hard to address.

Similarly, the language consisting of only the empty string is decidable, since an algorithm can examine the string and check whether it is empty or not.

The real challenge is proving that some problem ins't decidable. The main techniques are are diagonalization and reduction. Roughly speaking, proofs by diagonalization construct an input that every potential algorithm fails to address, using some kind of self-reference. A good example is the halting problem, much information on which is available online. Proofs by reduction show that if you could decide your problem X then you would be able to decide some other problem Y which is already known to be undecidable.


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.