12.1.1 Computability

Recall the following definition from Chapter 9.

Linz Definition 9.4 (Turing Computable): A function $f$ with domain $D$ is said to be Turing-computable, or just computable, if there exists some Turing machine $M = (Q, \Sigma, \Gamma, \delta, q_{0}, \Box, F)$ such that

$q_{0} w \vdash^{*}_{M} q_{f} f(w)$, $q_f \in F$,

for all $w \in D$.

Note:

• A function $f$ can be computable only if it is defined on the entire domain $D$.
• Otherwise, $f$ is uncomputable.
• So the domain of $f$ is crucial to the issue of computability.

12.1.2 Decidability

Here we work in a simplified setting: the result of a computation is either “yes” or “no”. In this context, the problem is considered either decidable or undecidable.

Problem: We have a set of related statements, each either true or false.

This problem is decidable if and only if there exists a Turing machine that gives the correct answer for every statement in the domain. Otherwise, the problem is undecidable.

Example problem statement: For a context-free grammar $G$, the language $L(G)$ is ambiguous. This is a true statement for some $G$ and false for others.

If we can answer this question, with either the result true or false, for every context-free grammar, then the problem is decidable. If we cannot answer the question for some context-free grammar (i.e., the Turing machine does not halt), then the problem is undecidable.

(In Linz Theorem 12.8, we see that this question is actually undecidable.)

12.1.3 The Turing Machine Halting Problem

Given the description of a Turing machine $M$ and input string $w$, does $M$, when started in the initial configuration $q_{0}w$, perform a computation that eventually halts?

What is the domain $D$?

• all Turing machines and all strings $w$ on the Turing machine’s alphabet

We cannot solve this problem by simulating $M$. That is an infinite computation if the Turing machine does not halt.

We must analyze the Turing machine description to get an answer for any machine $M$ and string $w$. But no such algorithm exists!

Linz Definition 12.1 (Halting Problem): Let $w_{M}$ be a string that describes a Turing machine $M = (Q, \Sigma, \Gamma, \delta, q_{0}, \Box, F)$ and let $w$ be a string in $M$’s alphabet. Assume that $w_{M}$ and $w$ are encoded as strings of 0’s and 1’s (as suggested in Linz Section 10.4). A solution to the halting problem is a Turing machine $H$, which for any $w_{M}$ and $w$, performs the computation

$q_{0}w_{M}w\ \vdash^{*}\ x_{1}q_{y}x_{2}$

if $M$ is applied to $w$ halts, and

$q_{0}w_{M}w\ \vdash^{*}\ y_{1}q_{n}y_{2}$,

if $M$ is applied to $w$ does not halt. Here $q_{y}$ and $q_{n}$ are both final states of $H$.

Linz Theorem 12.1 (Halting Problem is Undecidable): There does not exist any Turing machine $H$ that behaves as required by Linz Definition 12.1. Thus the halting problem is undecidable.

Proof: Assume there exists such a Turing machine $H$ that solves the halting problem.

The input to $H$ is $w_{M}w$, where $w_{M}$ is a description of Turing machine $M$. $H$ must halt with a “yes” or “no” answer as indicated in Linz Figure 12.1.

We next modify $H$ to produce a Turing machine $H'$ with the structure shown in Linz Figure 12.2.

When $H'$ reaches a state where $H$ halts, it enters an infinite loop.

From $H'$ we construct Turing machine $\hat{H}$, which takes an input $w_{M}$ and copies it, ending in initial state $q_{0}$ of $H'$. After that, it behaves the same as $H'$.

The behavior of $\hat{H}$ is

$q_{0}w_{M} \;\vdash^{*}_{\hat{H}}\; q_{0}w_{M}w_{M}$ $\;\vdash^{*}_{\hat{H}}\;\infty$

if $M$ applied to $w_{M}$ halts, and

$q_{0}w_{M} \;\vdash^{*}_{\hat{H}}\; q_{0}w_{M}w_{M}$ $\;\vdash^{*}_{\hat{H}}\; y_{1}q_{n}y_{2}$

if $M$ applied to $w_{M}$ does not halt.

Now $\hat{H}$ is itself a Turing machine, which can be also be encoded as a string $\hat{w}$.

So, let’s apply $\hat{H}$ to its own description $\hat{w}$. The behavior is

$q_{0}\hat{w} \;\vdash^{*}_{\hat{H}}\; \infty$

if $\hat{H}$ applied to $\hat{w}$ halts, and

$q_{0}\hat{w} \;\vdash^{*}_{\hat{H}}\; y_{1}q_{n}y_{2}$

if $M$ applied to $\hat{w}$ does not halt.

In the first case, $\hat{H}$ goes into an infinite loop (i.e., does not halt) if $\hat{H}$ halts. In the second case, $\hat{H}$ halts if $\hat{H}$ does not halt. This is clearly impossible!

Thus we have a contradiction. Therefore, there exists no Turing machine $H$. The halting problem is undecidable. QED.

It may be possible to determine whether a Turing machine halts in specific cases by analyzing the machine and its input.

However, this theorem says that there exists no algorithm to solve the halting problem for all Turing machines and all possible inputs.

Linz Theorem 12.2: If the halting problem were decidable, then every recursively enumerated language would be recursive. Consequently, the halting problem is undecidable.

Proof: Let $L$ be a recursively enumerable language on $\Sigma$, $M$ be a Turing machine that accepts $L$, and $w_{M}$ be an encoding of $M$ as a string.

Assume the halting problem is decidable and let $H$ be a Turing machine that solves it.

Consider the following procedure.

1. Apply $H$ to $w_{M}w$.
2. If $H$ says “no”, then $w \notin L$.
3. If $H$ says “yes”, then apply $M$ to $w$, which will eventually tell us whether $w \in L$ or $w \notin L$.

The above is thus a membership algorithm, so $L$ must be recursive. But we know that there are recursively enumerable languages that are not recursive. So this is a contradiction.

Therefore, $H$ cannot exist and the halting problem is undecidable. QED.

12.1.4 Reducing One Undecidable Problem to Another

In the above, the halting problem is reduced to a membership algorithm for recursively enumerable languages.

A problem $A$ is reduced to problem $B$ if the decidability of $B$ implies the decidability of $A$. We transform a new problem $A$ into a problem $B$ whose decidability is already known.

Note: The Linz textbook gives three example reductions in Section 12.1