Decidability in Theory of Computation

In this article, we have defined the concept of Decidability in Theory of Computation, Decidable Languages and which Languages are decidable and undecidable.

Table of contents:

  1. Definition of Decidability
  2. Which Languages are decidable?

Let us get started with Decidability in Theory of Computation.

Definition of Decidability

Decidability 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 decidable language if there exists a 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.

If the conditions hold, then A is known as a Decidable Language. If A does not hold the conditions, then A is an Undecidable Language.

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

Elements of a language A which is a Decidable Language is denoted as (C, w) where C is the computational model (Turing Machine or Pushdown Automaton) w is the string

Which Languages are decidable?

There are 4 types of Languages which we will define further:

  • Language ADFA
  • Language ANFA
  • Language ACFG
  • Language ATM

Let us dive into the Languages further.

Language ADFA

Language ADFA is defined as follows:

{ (M ,w) : M is a Deterministic Finite Automaton (DFA) that accepts the string w }

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

The language Language ADFA is Decidable Language.

Language ANFA

Language ANFA is defined as follows:

{ (M ,w) : M is a Non-Deterministic Finite Automaton (NFA) that accepts the string w }

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

The language Language ANFA is Decidable Language.

Language ACFG

Language ACFG is defined as follows:

{ (M ,w) : M is a Context Free Grammar (CFG) that accepts the string w }

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

The language Language ACFG is Decidable Language.

Language ATM

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 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 Decidability in Theory of Computation.