# Undecidability in Theory of Computation

Get FREE domain for 1st year and build your brand new site

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.