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:

  1. Definition of Undecidability
  2. Language ATM 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:

  1. If w belongs to A, then the computation of Turing Machine M on w as input, ends in the accept state.
  2. 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 ATM in undecidable

Language ATM 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 ACFG 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 ADFA Deterministic Finite Automaton Yes
Language ANFA Non-Deterministic Finite Automaton Yes
Language ACFG Context Free Grammar (CFG) Yes
Language ATM 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.