ABSTRACT
In Chapter 9, we have considered Turing machines (TMs) as language acceptors by analogy with other language acceptors, such as finite and pushdown automata, discussed earlier in this book� In this chapter, we make use of TMs to show the fundamentals of theory of computation, which is primarily oriented toward determining the theoretical limits of computation in general� This orientation comes as no surprise: by the Church-Turing thesis, which opened Section IV of this book, every procedure can be formalized by a TM, so any computation beyond the power of TMs is also beyond the computer power in general�
This two-section chapter gives an introduction to two key areas of the theory of computationcomputability and decidability� In Section 10�1, regarding computability, we view TMs as computers of functions over nonnegative integers and show the existence of functions whose computation cannot be specified by any procedure� Then, regarding decidability, we formalize algorithms that decide problems by using TMs that halt on every input in Section 10�2, which is divided into five subsections� In Section 10�2�1, we conceptualize this approach to decidability� In Section 10�2�2, we formulate several important problems concerning the language models discussed in Chapters 3 and 6, such as finite automata (FAs) and context-free grammars (CFGs), and construct algorithms that decide them� In Section 10�2�3, more surprisingly, we present problems that are algorithmically undecidable, and in Section 10�2�4, we approach undecidability from a more general viewpoint� Finally, in Section 10�2�5, we reconsider algorithms that decide problems in terms of their computational complexity measured according to time and space requirements� Perhaps most importantly, we point out that although some problems are decidable in principle, they are intractable for unreasonably high computational requirements of the algorithms that decide them�
214
10.1 Computability Considering the TM model as the formalization of an effective procedure, we show the existence of functions whose computation cannot be specified by any procedure, so they can never be computed by any computer� As a matter of fact, the existence of these uncomputable functions immediately follows from the following counting argument� Consider the set of all functions that map ℕ onto {0, 1} and the set of all procedures� Whereas the former is uncountable, the latter is countable under our assumption that every procedure has a finite description (see Section 9�1)� Thus, there necessarily exist functions with no procedures to compute them� In this section, based on the following TM-based formalization, we take a more specific look at functions whose computation can or, in contrast, cannot be specified by any procedure�
Definition 10.1 Let M ∈ TMΨ� The function computed by M, symbolically denoted by M-f, is defined over Δ* as M-f = {(x, y)| x, y ∈ Δ*, ▹▸x◃ ⇒* ▹▪yu◃ in M, u ∈ {▫}*}�
Consider M-f, where M ∈ TMΨ, and an argument x ∈ Δ*� In a general case, M-f is partial, so M-f(x) may or may not be defined� Clearly, if M-f(x) = y is defined, M computes ▹▸x◃ ⇒* ▹▪yu◃, where u ∈ {▫}*� However, if M-f(x) is undefined, M, starting from ▹▸x◃, never reaches a configuration of the form ▹▪vu◃, where v ∈ Δ* and u ∈ {▫}*, so it either rejects x or loops on x (see Convention 9�8)�
Definition 10.2 A function f is a computable function if there exists M ∈ TMΨ such that f = M-f; otherwise, f is an uncomputable function�
10.1.1 Integer Functions Computed by Turing Machines By Definition 10�1, for every M ∈ TMΨ, M-f is defined over Δ*, where Δ is an alphabet� However, in mathematics, we usually study numeric functions defined over sets of infinitely many numbers� To use TMs to compute functions like these, we first need to represent these numbers by strings over Δ� In this introductory book, we restrict our attention only to integer functions over 0ℕ, so we need to represent every nonnegative integer i ∈ 0ℕ as a string over Δ� Traditionally, we represent i in unary as unary(i) for all i ∈ 0ℕ, where unary is defined in Example 2�4� That is, unary( j) = a j for all j ≥ 0; for instance, unary(0), unary(2), and unary(999) are equal to ε, aa, and a999, respectively� Under this representation, used in the sequel, we obviously automatically assume that Δ = {a} simply because a is the only input symbol needed� Next, we formalize the computation of integer functions by TMs based on unary�
Definition 10.3
I� Let g be a function over 0ℕ and M ∈ TMΨ� M computes g in unary or, more briefly, M computes g iff unary(g) = M-f�
II� A function h over 0ℕ is a computable function if there exists M ∈ TMΨ such that M computes h; otherwise, h is an uncomputable function�
In greater detail, part I of Definition 10�3 says that M computes an integer function g over 0ℕ if this equivalence holds: g(x) = y iff (unary(x), unary(y)) ∈ M-f, for all x, y ∈ 0ℕ
Convention 10.4 Whenever M ∈ TMΨ works on an integer x ∈ 0ℕ, x is expressed as unary(x)� For brevity, whenever no confusion exists, instead of stating that M works on x represented as unary(x), we just state that M works on x in what follows�
Example 10.1 Let g be the successor function defined as g(i) = i + 1, for all i ≥ 0� Construct a TM M that computes ▹▸ai◃ ⇒* ▹▪ai+1◃ so it moves across ai to the right bounder ◃, replaces it with a◃, and returns to the left to finish its accepting computation in ▹▪ai+1◃� As a result, M increases the number of as by one on the tape� Thus, by Definition 10�3, M computes g�
Example 10.2 Let g be the total function defined as g(i) = j, for all i ≥ 0, where j is the smallest prime satisfying i ≤ j� Construct a TM M that tests whether i, represented by ai, is a prime in the way described in Example 9�2� If i is prime, M accepts in the configuration ▹▪ai◃� If not, M continues its computation from ▹▸ai+1◃ and tests whether i + 1 is prime; if it is, it accepts in ▹▪ai+1◃� In this way, it continues increasing the number of as by one and testing whether the number is prime until it reaches a j such that j is prime� As this prime j is obviously the smallest prime satisfying i ≤ j, M accepts in ▹▪a j◃� Thus, M computes g�
Both functions discussed in Examples 10�1 and 10�2 are total� However, there also exist partial integer functions, which may be undefined for some arguments� Suppose that g is a function over 0ℕ, which is undefined for some arguments� Let M ∈ TMΨ compute g� According to Definition 10�3, for any x ∈ 0ℕ, g(x) is undefined iff (unary(x), unary(y)) ∉ M-f for all y ∈ 0ℕ� Example 10�3 illustrates a partial integer function computed in this way�
Convention 10.5 As opposed to Examples 10�1 and 10�2, the next function as well as all other functions discussed throughout the rest of this section is defined over the set of positive integers, ℕ, which excludes 0�
Example 10.3 In this example, we consider a partial function g over ℕ that is defined for 1, 2, 4, 8, 16, …, but it is undefined for the other positive integers� More precisely, g(x) = 2x if x = 2n, for some n ∈ ℕ; otherwise, g(x) is undefined (see Figure 10�1)�
We construct M ∈ TMΨ that computes g as follows� Starting from ▹▸ai◃, M computes ▹▸ai◃ ⇒ *
▹▸aiAj◃ with j being the smallest natural number simultaneously satisfying i ≤ j and j = 2n with n ∈ ℕ� If i = j, then i = 2n and g(i) = 2i = 2n+1, so M computes ▹▸aiAj◃ ⇒* ▹▪aiaj◃ and, thereby, defines g(i) = 2n+1� If i < j, then 2n−1 < i < 2n and g(i) is undefined, so M rejects ai by ▹▸aiAj◃ ⇒* ▹♦ai▫j◃�
In somewhat greater detail, we describe M by the following Pascal-like algorithm that explains how M changes its configurations�
Figure 10.1 Partial function g discussed in Example 10.3.
