Short Notes: Undecidability | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 Page 1


There are two types of TMs (based on halting):
1. Halting TM : (Accepts Recursive languages): TMs that always halt, no matter 
accepting or non no matter accepting or non-accepting (called as decidable 
problems)
2. TM : (Accepts Recursively enumerable): TMs that are guaranteed to halt are 
guaranteed to halt only on acceptance only on acceptance. If non-accepting, it 
may or may not halt (i.e., could loop forever). (Either decidable or partially 
decidable)
Decidable Problem
• If there is a Turing machine that decides the problem, called as Decidable 
problem.
• A decision problem that can be solved by an algorithm that halts on all inputs 
In a finite number of steps.
• A problem Is decidable, if there is an algorithm that can answer either yes or 
no.
• A language for which membership can be decided by an algorithm that halts 
on all inputs in a finite number of steps.
• Decidable problem Is also called as totally decidable problem, algorithmically 
solvable, recursively solvable.
Undecidable Problem (Semi-dedidable or Totally not decidable)
• A problem that cannot be solved for all cases by any algorithm whatsoever.
• Equivalent Language cannot be recognized by a Turing machine that halts for 
all inputs.
The following problems are undecidable problems:
Page 2


There are two types of TMs (based on halting):
1. Halting TM : (Accepts Recursive languages): TMs that always halt, no matter 
accepting or non no matter accepting or non-accepting (called as decidable 
problems)
2. TM : (Accepts Recursively enumerable): TMs that are guaranteed to halt are 
guaranteed to halt only on acceptance only on acceptance. If non-accepting, it 
may or may not halt (i.e., could loop forever). (Either decidable or partially 
decidable)
Decidable Problem
• If there is a Turing machine that decides the problem, called as Decidable 
problem.
• A decision problem that can be solved by an algorithm that halts on all inputs 
In a finite number of steps.
• A problem Is decidable, if there is an algorithm that can answer either yes or 
no.
• A language for which membership can be decided by an algorithm that halts 
on all inputs in a finite number of steps.
• Decidable problem Is also called as totally decidable problem, algorithmically 
solvable, recursively solvable.
Undecidable Problem (Semi-dedidable or Totally not decidable)
• A problem that cannot be solved for all cases by any algorithm whatsoever.
• Equivalent Language cannot be recognized by a Turing machine that halts for 
all inputs.
The following problems are undecidable problems:
• Halting Problem: A halting problem is undecidable problem. There is no 
general method or algorithm which can solve the halting problem for all 
possible inputs.
• Emptyness Problem: Whether a given TM accepts Empty?
• Finiteness Problem: Whether a given TM accepts Finite?
• Equivalence Problem: Whether Given two TM’s produce same language?. Is 
L(TM1) = L(TM2) ?
• Is L(TM1) C L(TM2) ? (Subset Problem)
• Is L(TM1) fl L(TM2) = CFL?
• Is L(TM1) = Z* ? (Totality Problem)
• Is the complement of L(G1) context-free ?
Undecidable problems are two types: Partially decidable (Semi-decidable) and 
Totally not decidable.
• Semi decidable: A problem is semi-decidable if there is an algorithm that says 
yes. if the answer is yes, however it may loop infinitely if the answer is no.
• Totally not decidable (Not partially decidable): A problem is not decidable if 
we can prove that there is no algorithm that will deliver an answer.
Jot Partially 
Decidable
Undecidable
(Partially Decidable)
D E C ID A B L E
Ccmpiowry 
... TTwaiy *
Prtil
P roblem /
Halting
Problem 
Answers YES. if Yes 
W o answer, if N o ,
Decidability table for Formal Languages:
Problems RL DC CFL Rec RE
Membership Y Y Y Y N
Finiteness Y Y Y N N
Page 3


There are two types of TMs (based on halting):
1. Halting TM : (Accepts Recursive languages): TMs that always halt, no matter 
accepting or non no matter accepting or non-accepting (called as decidable 
problems)
2. TM : (Accepts Recursively enumerable): TMs that are guaranteed to halt are 
guaranteed to halt only on acceptance only on acceptance. If non-accepting, it 
may or may not halt (i.e., could loop forever). (Either decidable or partially 
decidable)
Decidable Problem
• If there is a Turing machine that decides the problem, called as Decidable 
problem.
• A decision problem that can be solved by an algorithm that halts on all inputs 
In a finite number of steps.
• A problem Is decidable, if there is an algorithm that can answer either yes or 
no.
• A language for which membership can be decided by an algorithm that halts 
on all inputs in a finite number of steps.
• Decidable problem Is also called as totally decidable problem, algorithmically 
solvable, recursively solvable.
Undecidable Problem (Semi-dedidable or Totally not decidable)
• A problem that cannot be solved for all cases by any algorithm whatsoever.
• Equivalent Language cannot be recognized by a Turing machine that halts for 
all inputs.
The following problems are undecidable problems:
• Halting Problem: A halting problem is undecidable problem. There is no 
general method or algorithm which can solve the halting problem for all 
possible inputs.
• Emptyness Problem: Whether a given TM accepts Empty?
• Finiteness Problem: Whether a given TM accepts Finite?
• Equivalence Problem: Whether Given two TM’s produce same language?. Is 
L(TM1) = L(TM2) ?
• Is L(TM1) C L(TM2) ? (Subset Problem)
• Is L(TM1) fl L(TM2) = CFL?
• Is L(TM1) = Z* ? (Totality Problem)
• Is the complement of L(G1) context-free ?
Undecidable problems are two types: Partially decidable (Semi-decidable) and 
Totally not decidable.
• Semi decidable: A problem is semi-decidable if there is an algorithm that says 
yes. if the answer is yes, however it may loop infinitely if the answer is no.
• Totally not decidable (Not partially decidable): A problem is not decidable if 
we can prove that there is no algorithm that will deliver an answer.
Jot Partially 
Decidable
Undecidable
(Partially Decidable)
D E C ID A B L E
Ccmpiowry 
... TTwaiy *
Prtil
P roblem /
Halting
Problem 
Answers YES. if Yes 
W o answer, if N o ,
Decidability table for Formal Languages:
Problems RL DC CFL Rec RE
Membership Y Y Y Y N
Finiteness Y Y Y N N
Emptiness Y Y Y N N
Equivalence Y Y N N N
Is L1 c L2 ?(SUBSET) Y N N N N
Is L = REGULAR? Y Y N N N
Is L Ambiguous? Y N N N N
L=?(UNIVERSAL) Y Y N N N
L1 F I L2= 0 > ?(DISJOINT) Y N N N N
Is L= Regular? Y Y N N N
L1 n L2= L Y N N Y Y
Is L ' also same type? Y Y N Y N
Notes : RL= Regular Language, DC = Deterministic context-free languages (DCFL), 
CFL= Context Free Languages (CFL), Rec = Recursive language, RE= Recusively 
Enumerable Language.