Undecidability

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.

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: A problem is not decidable if we can prove that there is no algorithm that will deliver an answer.

Compcollection