# Undecidability in Theory of Computation

In this article, we have explained concept of Undecidability in Theory of Computation along with idea of undecidable languages like Halting Problem.

Prerequisite: Decidability in Theory of Computation

Table of contents:

- Definition of Undecidability
- Language A
_{TM}in undecidable

Let us get started with Undecidability in Theory of Computation.

# Definition of Undecidability

Undecidability is defined as follows:

Î£ is a set of alphabet and A is a Language such that A is proper subset of Î£*. Î£* is a set of all possible strings.

A is a undecidable language if there exists **NO Computational Model** (such as Turing Machine) M such that for every string w that belong to Î£*, the following two conditions hold:

- If w belongs to A, then the computation of Turing Machine M on w as input, ends in the accept state.
- If w does not belong to A, then computation of Turing Machine M on w, ends in the reject state.

Note there may be a Computation Machine M for which one condition hold but does not hold both conditions.

A is an **Undecidable Language**.

In simple words, A is a undecidable language if there is **NO** Turing Machine or an Algorithm that correctly tells if a given string w is a part of the language or not in finite time.

# Language A_{TM} in undecidable

Language A_{TM} is defined as follows:

{ (M ,w) : M is a Turing Machine (TM) that accepts the string w }

Therefore, in this language DFA is enough. We do not need stronger models.

The language Language A_{CFG} is Undecidable Language.

Note this is the only undecidable language. This means that there exists no Algorithm that can determine if a given Algorithm M can accept or not a given string w in finite time.

The decidability and undecidability of each language can be proved. We have omitted the proof of these for now. The summary is as follows:

Language | Machine | Decidability |
---|---|---|

Language A_{DFA} |
Deterministic Finite Automaton | Yes |

Language A_{NFA} |
Non-Deterministic Finite Automaton | Yes |

Language A_{CFG} |
Context Free Grammar (CFG) | Yes |

Language A_{TM} |
Turing Machine (TM) | No |

The Halting Problem Halt is defined as:

Halt = { (P, w) : P is a program that terminates execution with w as input }.

The Language Halt is undecidable.

With this article at OpenGenus, you must have the complete idea of Undecidability in Theory of Computation.