Decidability
Rimsha Kanwal (1079-FBAS/MSCS/F20)
Rimsha Kanwal (1080-FBAS/MSCS/F20)
Decidability:
• If there exist an algorithm that takes an input as instance of the problem
and determines whether answer to that instance is “yes” or “no”
• For example as an computer engineer we look for what is problem
statement and can we solve it by using any kind of language or program or
algorithm.
PROBLEM
ALGORITHM No ALGORITHM
(Decidable) (Undecidable)
• In simple words, for any problem if it is solvable than the next step is to deciding whether
we can write a step by step solution for it or not. And either it (algorithm) can work
properly or not.
Decidable Language in Theory of Computation?
Let suppose we take language and many strings can be developed by that language
or (language has a set of many string). Now at an instance we take a string as an
input then we will check it on Turing machine ,whether the Turing machine accepts
or rejects and this gives the output as a result , than it shows that machine is properly
working for every input and gives the output in the form of acceptance or rejection,
this language is called decidable language.
“The language L from which when any string is taken as input and machine
easily tells either it is accepted or non-accepted, is called Decidable language.”
Continued…………
Every decidable language is Turing-Acceptable.
A decision problem P is said to be decidable (i.e., have an algorithm) if the language L of
all yes instances to P is decidable.
A decision problem P is said to be semi-decidable (i.e., have a semi-algorithm) if the
language L of all yes instances to P is recursive enumerable language.
A decision problem P is said to be undecidable if the language L of all yes instances to P is
not decidable.
Diagram:
Non-
Turing acceptable
Turing
languages
acceptable
languages Decidable
languages
Continued…………..
For a decidable language, for each input string, the Turing machine halts
either at the accept or the reject state as depicted in the following diagram:
Decision on Halt
Input Rejected
Accepted
Turing Machine
Examples……
Example 1:
Problem:
• Find out whether the following problem is decidable or not
Is a number ‘m’ prime?
Solution
1) Prime numbers = {2, 3, 5, 7, 11, 13, …………..}
2) Divide the number ‘m’ by all the numbers between ‘2’ and ‘m’. ‘m’ is starting
from ‘2’.
3) 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
Continued……………….
Example 2:
Problem
• Given a regular language L and string w, how can we check if w ∈ L?
Solution
1) Take the DFA that accepts L and check if w is accepted
w∈L
Qr
Input string w
Qi
w∈L
Qf
DFA
Continued…………...
Some Notations:
'RL' implies Regular language.
'CFL' implies Context free language.
'DCFL' implies deterministic context free language.
'CSL' implies Context sensitive language.
'REC.L' implies Recursive language.
'REL' implies Recursive enumerable language.
'D' implies that the problem is decidable.
'UD' implies that the problem is undecidable.
Continued………….
Problems RL DCFL CFL CSL Rec.L REL
Does ‘w’ belongs to language L?
D D D D D UD
Is L= null?
D D D UD UD UD
Is L= E*
D D UD UD UD UD
Is L1= L2 ?
D D UD UD UD UD
Is L1 subset of L2 ?
D UD UD UD UD UD
Is L1 intersection of L2= null?
D UD UD UD UD UD
Is ‘L’ finite or not?
D D D UD UD UD
Continued…………
Problems RL DCFL CFL CSL Rec.L REL
Is compliment of ‘L’ a
language of same type or D D UD D D UD
not?
Is intersection of two
languages of same type or D UD UD D D D
not?
Is ‘L’ regular language or D D UD UD UD UD
not?
Important Points:
1) If a language L is decidable, then its complement L' is also decidable.
2) If a language is decidable, then there is an enumerator for it.
Some Notations:
We recall the following basic notions.
1) A decidable problem is a restricted type of an algorithmic problem where
for each input there are only two possible outputs.
2) A decidable algorithm is an algorithm that computes the correct truth value
for each input instance of a decision problem. The algorithm has to
terminate on all inputs!
3) A decidable problem is decidable if there exists a decision algorithm for it.
Otherwise it is undecidable.
