a language is called decidable or recursive if there is a turing machine which accepts and halts on every input string w. every decidable language is turing-acceptable.

a decision problem p is decidable if the language l of all yes instances to p is decidable.

for a decidable language, for each input string, the tm halts either at the accept or the reject state as depicted in the following diagram −

example 1

find out whether the following problem is decidable or not −

is a number ‘m’ prime?

solution

prime numbers = {2, 3, 5, 7, 11, 13, …………..}

divide the number ‘m’ by all the numbers between ‘2’ and ‘√m’ starting from ‘2’.

if any of these numbers produce a remainder zero, then it goes to the “rejected state”, otherwise it goes to the “accepted state”. so, here the answer could be made by ‘yes’ or ‘no’.

hence, it is a decidable problem.

example 2

given a regular language l and string w, how can we check if w ∈ l?

solution

take the dfa that accepts l and check if w is accepted

some more decidable problems are −

• does dfa accept the empty language?
• is l₁ ∩ l₂ = ∅ for regular sets?

note −

• if a language l is decidable, then its complement l' is also decidable

• if a language is decidable, then there is an enumerator for it.