Study Notes on Undecidability

By Mukesh Kumar|Updated : December 3rd, 2021

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) ⊆ 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.
 byjusexamprep
 
 

 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

Comments

write a comment
Prateek Gupta
What type of questions come from this topic?

Follow us for latest updates