# Decidability in Theory of Computation

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

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:

- Definition of Decidability
- 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:

- 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.

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 A
_{DFA} - Language A
_{NFA} - Language A
_{CFG} - Language A
_{TM}

Let us dive into the Languages further.

### Language A_{DFA}

Language A_{DFA} 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 A_{DFA} is Decidable Language.

### Language A_{NFA}

Language A_{NFA} 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 A_{NFA} is Decidable Language.

### Language A_{CFG}

Language A_{CFG} 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 A_{CFG} is Decidable Language.

### Language A_{TM}

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