# Study Notes on Undecidability

By BYJU'S Exam Prep

Updated on: September 25th, 2023

## 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.

### 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:

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!