Study Notes on Undecidability
By BYJU'S Exam Prep
Updated on: September 25th, 2023
There are two types of TMs (based on halting):
- Halting TM : (Accepts Recursive languages) : TMs that always halt, no matter accepting or non no matter accepting or non-accepting (called as decidable problems)
- 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)
Table of content
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) ⊆ L(TM2) ? (Subset Problem)
- Is L(TM1) Ո L(TM2) = CFL?
- Is L(TM1) = Σ* ? (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.
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 ⊆ 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 ∩ L2= Ф ?(DISJOINT) |
Y |
N |
N |
N |
N |
|
Is L= Regular? |
Y |
Y |
N |
N |
N |
|
L1 ∩ 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.
You can follow the detailed champion study plan for GATE CS 2021 from the following link:
Detailed GATE CSE 2021 Champion Study Plan
Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU’S Exam Prep Test Series check the following link:
Click Here to Avail GATE CSE Test Series!(100+ Mock Tests)
Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:
Click here to avail Online Classroom Program for Computer Science Engineering
Thanks
The Most Comprehensive Exam Prep App!
Download BYJU’S Exam Prep, Best gate exam app for Preparation
