Decidability

Overview

A Turing machine that halts on all inputs is called a decider. A decider that recognizes some language is said to decide that language. A language is Turing-decidable (or decidable or recursive) if a Turing machine decides it.

Closure Operations

Let $A$ and $B$ be decidable languages. Such languages are closed under the following:

Union: $A \cup B$
Intersection: $A \cap B$
Complement: $\overset{―}{A}$
Concatenation: $A \circ B$
Kleene Star: $A^{*}$

Furthermore, a language is decidable if and only if both it and its complement are Turing-recognizable.

Undecidability

A language is undecidable if no Turing machine can decide it. Proving undecidability is usually done by performing a reduction on an undecidable language.

Halting Problem

The halting problem refers to the problem of determining, from a description of an arbitrary computer program and an input, whether the program will eventually halt. In particular, it refers to the decidability of language

A = {⟨ M, w ⟩ ∣ M is a Turing machine and M halts on w} .

It is the classic example of an undecidable problem.

Post Correspondence Problem

Define a finite collection of dominos $P$ as:

P = {[\frac{t_{1}}{b_{1}}], [\frac{t_{2}}{b_{2}}], \dots, [\frac{t_{n}}{b_{n}}]}

A match is a sequence of dominos $i_{1}, i_{2}, i_{k}$ such that the strings generated by concatenating all the top symbols and all the bottom symbols are equal:

t_{i_{1}} t_{i_{2}} \dots t_{i_{k}} = b_{i_{1}} b_{i_{2}} \dots b_{i_{k}}

The post correspondence problem is the problem of determining whether such a set of dominos has a match.

Rice's Theorem

Let $P$ be a language consisting of Turing machine descriptions. Suppose that $P$ is:

Nontrivial. It is neither empty nor the set of all TM descriptions.
Extensional. If $L (M_{1}) = L (M_{2})$ , then $M_{1} \in P ⟺ M_{2} \in P$ .

Then $P$ is undecidable.