Notes on Models of Computation
Chapter 12

H. Conrad Cunningham

06 April 2022

Copyright (C) 2015, 2022, H. Conrad Cunningham
Professor of Computer and Information Science
University of Mississippi
214 Weir Hall
P.O. Box 1848
University, MS 38677
(662) 915-7396 (dept. office)

Browser Advisory: The HTML version of this textbook requires a browser that supports the display of MathML. A good choice as of April 2022 is a recent version of Firefox from Mozilla.

Note: These notes were written primarily to accompany my use of Chapter 1 of the Linz textbook An Introduction to Formal Languages and Automata [[1].

12 Limits of Algorithmic Computation

In Linz Chapter 9, we studied the Turing thesis, which concerned what Turing machines can do.

This chapter we study: What Turing machines cannot do.

This chapter considers the concepts:

12.1 Some Problems That Cannot Be Solved with Turing Machines

12.1.1 Computability

Recall the following definition from Chapter 9.

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

q0wM*qff(w)q_{0} w \vdash^{*}_{M} q_{f} f(w), qfFq_f \in F,

for all wDw \in D.

Note:

  • A function ff can be computable only if it is defined on the entire domain DD.
  • Otherwise, ff is uncomputable.
  • So the domain of ff 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 GG, the language L(G)L(G) is ambiguous. This is a true statement for some GG 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 MM and input string ww, does MM, when started in the initial configuration q0wq_{0}w, perform a computation that eventually halts?

What is the domain DD?

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

We cannot solve this problem by simulating MM. 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 MM and string ww. But no such algorithm exists!

Linz Definition 12.1 (Halting Problem): Let wMw_{M} be a string that describes a Turing machine M=(Q,Σ,Γ,δ,q0,,F)M = (Q, \Sigma, \Gamma, \delta, q_{0}, \Box, F) and let ww be a string in MM’s alphabet. Assume that wMw_{M} and ww 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 HH, which for any wMw_{M} and ww, performs the computation

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

if MM is applied to ww halts, and

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

if MM is applied to ww does not halt. Here qyq_{y} and qnq_{n} are both final states of HH.

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

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

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

Linz Fig. 12.1: Turing Machine H

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

Linz Fig. 12.2: Turing Machine H'

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

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

The behavior of Ĥ\hat{H} is

q0wMĤ*q0wMwMq_{0}w_{M} \;\vdash^{*}_{\hat{H}}\; q_{0}w_{M}w_{M} Ĥ*\;\vdash^{*}_{\hat{H}}\;\infty

if MM applied to wMw_{M} halts, and

q0wMĤ*q0wMwMq_{0}w_{M} \;\vdash^{*}_{\hat{H}}\; q_{0}w_{M}w_{M} Ĥ*y1qny2\;\vdash^{*}_{\hat{H}}\; y_{1}q_{n}y_{2}

if MM applied to wMw_{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

q0ŵĤ*q_{0}\hat{w} \;\vdash^{*}_{\hat{H}}\; \infty

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

q0ŵĤ*y1qny2q_{0}\hat{w} \;\vdash^{*}_{\hat{H}}\; y_{1}q_{n}y_{2}

if MM 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 HH. 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 LL be a recursively enumerable language on Σ\Sigma, MM be a Turing machine that accepts LL, and wMw_{M} be an encoding of MM as a string.

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

Consider the following procedure.

  1. Apply HH to wMww_{M}w.
  2. If HH says “no”, then wLw \notin L.
  3. If HH says “yes”, then apply MM to ww, which will eventually tell us whether wLw \in L or wLw \notin L.

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

Therefore, HH 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 AA is reduced to problem BB if the decidability of BB implies the decidability of AA. We transform a new problem AA into a problem BB whose decidability is already known.

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

12.2 Undecidable Problems for Recursively Enumerable Languages

Linz Theorem 12.3 (Empty Unrestricted Grammars Undecidable): Let GG be an unrestricted grammar. Then the problem of determining whether or not

L(G)=L(G) = \emptyset

is undecidable.

Proof: See Linz Section 12.2 for the details of this reduction argument. The decidability of membership problem for recursively enumerated languages implies the problem in this theorem.

Linz Theorem 12.4 (Finiteness of Turing Machine Languages is Undecided): Let MM be a Turing Machine. Then the question of whether or not L(M)L(M) is finite is undecidable.

Proof: See Linz Section 12.2 for the details of this proof.

Rice’s theorem, a generalization of the above, states that any nontrivial property of a recursively enumerable language is undecidable. The adjective “nontrivial” refers to a property possessed by some but not all recursively enumerated languages.

12.3 The Post Correspondence Problem

This section is not covered in this course.

12.4 Undecidable Problems for Context-Free Languages

Linz Theorem 12.8: There exists no algorithm for deciding whether any given context-free grammar is ambiguous.

Proof: See Linz Section 12.4 for the details of this proof.

Linz Theorem 12.9: There exists no algorithm for deciding whether or not

L(G1)L(G2)=L(G_{1}) \cap L(G_{2}) = \emptyset

for arbitrary context-free grammars G1G_{1} and G2G_{2}.

Proof: See Linz Section 12.4 for the details of this proof.

Keep in mind that the above and other such decidability results do not eliminate the possibility that there may be specific cases–perhaps even many interesting and important cases–for which there exist decision algorithms.

However, these theorems do say that there are no general algorithms to decide these problems. There are always some cases in which specific algorithms will fail to work.

12.5 A Question of Efficiency

This section is not covered in this course.

12.6 References

[1]
Peter Linz. 2011. Formal languages and automata (Fifth ed.). Jones & Bartlett, Burlington, Massachusetts, USA.