| Preface |
|
xv | |
|
|
|
1 | (46) |
|
1 Introducing Computation Theory |
|
|
3 | (12) |
|
1.1 The Autobiographical (ALR) Seeds of Our Framework |
|
|
4 | (3) |
|
1.1.1 Computation by "Shapeless" Agents and Devices |
|
|
4 | (2) |
|
1.1.2 Computation Theory as a Study of Computation |
|
|
6 | (1) |
|
1.2 The Highlights of Our Framework: How We Tell the Story |
|
|
7 | (3) |
|
1.3 Why Is a New Computation Theory Text Needed? |
|
|
10 | (5) |
|
|
|
15 | (32) |
|
2.1 Computation Theory as a Branch of Discrete Mathematics |
|
|
17 | (3) |
|
2.1.1 Dynamism Within Traditional Mathematics |
|
|
17 | (1) |
|
2.1.2 Discrete Mathematics with Computational Objects |
|
|
17 | (3) |
|
2.2 The Four Pillars of Computation Theory |
|
|
20 | (12) |
|
|
|
21 | (1) |
|
|
|
22 | (4) |
|
2.2.3 Pillar ℵ: nondeterminism |
|
|
26 | (3) |
|
2.2.4 Pillar B: presentation/specification |
|
|
29 | (1) |
|
|
|
30 | (2) |
|
2.3 A Map of the Book by
Chapter |
|
|
32 | (4) |
|
2.4 Ways of Using this Book |
|
|
36 | (10) |
|
2.4.1 As a Text for a "Classical" Theory Course |
|
|
36 | (1) |
|
2.4.1.1 Automata and Formal Languages |
|
|
37 | (1) |
|
2.4.1.2 Computability Theory |
|
|
37 | (1) |
|
2.4.1.3 Complexity Theory |
|
|
38 | (1) |
|
2.4.2 As a Primary Text: "Big Ideas in Computation" |
|
|
39 | (3) |
|
2.4.3 As a Supplemental Text: "Theoretical Aspects of-" |
|
|
42 | (1) |
|
2.4.3.1 Pervasive Topics: Enhance Many Courses |
|
|
42 | (2) |
|
2.4.3.2 Focused Topics: Enhance Specialized Courses |
|
|
44 | (2) |
|
2.5 Tools for Using the Book |
|
|
46 | (1) |
|
|
|
47 | (154) |
|
3 Pure State-Based Computational Models |
|
|
51 | (28) |
|
3.1 Online Automata and Their Languages |
|
|
51 | (13) |
|
3.1.1 Basics of the OA Model |
|
|
51 | (6) |
|
3.1.2 Preparing to Understand the Notion State |
|
|
57 | (5) |
|
3.1.3 A Myhill-Nerode-like Theorem for OAs |
|
|
62 | (2) |
|
3.2 Finite Automata and Regular Languages |
|
|
64 | (15) |
|
3.2.1 Overview and History |
|
|
64 | (3) |
|
3.2.2 Perspectives on Finite Automata |
|
|
67 | (1) |
|
3.2.2.1 The FA as an Abstract Model |
|
|
68 | (2) |
|
3.2.2.2 On Designing FAs for Specific Tasks |
|
|
70 | (5) |
|
3.2.3 Why FAs Get Confused: a Consequence of Finiteness |
|
|
75 | (4) |
|
4 The Myhill-Nerode Theorem: Implications and Applications |
|
|
79 | (40) |
|
4.1 The Myhill-Nerode Theorem for FAs |
|
|
80 | (8) |
|
4.1.1 The Theorem: States Are Equivalence Classes |
|
|
81 | (2) |
|
4.1.2 What Do ≡L-Equivalence Classes Look Like? |
|
|
83 | (1) |
|
4.1.2.1 Language #1: L1 ≡ {ai | i ≡ 0 mod 3} |
|
|
83 | (2) |
|
4.1.2.2 Language #2: L2 ≡ {x1111y | x,y e {0, 1}*} |
|
|
85 | (1) |
|
4.1.2.3 Language #3: L3 ≡ {anbn | n e N} |
|
|
86 | (1) |
|
4.1.2.4 The Language of (Binary) Palindromes |
|
|
87 | (1) |
|
4.2 Sample Applications of the Myhill-Nerode Theorem |
|
|
88 | (31) |
|
4.2.1 Proving that Languages Are Not Regular |
|
|
88 | (3) |
|
4.2.2 On Minimizing Finite Automata |
|
|
91 | (1) |
|
4.2.2.1 The FA State-Minimization Algorithm |
|
|
92 | (4) |
|
4.2.3 Two-Way (Offline) Finite Automata |
|
|
96 | (5) |
|
4.2.4 Finite Automata with Probabilistic Transitions |
|
|
101 | (1) |
|
4.2.4.1 PFAs and Their Languages |
|
|
101 | (2) |
|
4.2.4.2 PEA Languages and Regular Languages |
|
|
103 | (1) |
|
A PEA languages which are not Regular |
|
|
103 | (6) |
|
B PEA languages which are Regular |
|
|
109 | (3) |
|
4.2.5 State as a Memory-Constraining Resource |
|
|
112 | (2) |
|
4.2.5.1 Approximating OAs by Growing FAs: Examples |
|
|
114 | (1) |
|
4.2.5.2 Approximating OAs by Growing FAs: General Case |
|
|
115 | (4) |
|
5 Online Turing Machines and the Implications of Online Computing |
|
|
119 | (20) |
|
5.1 Online Turing Machines: Realizations of Infinite OAs |
|
|
120 | (9) |
|
5.1.1 OTMs with Abstract Storage Devices |
|
|
120 | (2) |
|
5.1.2 OTMs with Linear Tapes for Storage |
|
|
122 | (7) |
|
5.2 The Nature of Online Computing |
|
|
129 | (10) |
|
5.2.1 Online TMs with Multiple Complex Tapes |
|
|
130 | (2) |
|
5.2.2 An Information-Retrieval Problem as a Language |
|
|
132 | (2) |
|
5.2.3 The Impact of Tape Structure on Memory Locality |
|
|
134 | (1) |
|
5.2.4 Tape Dimensionality and the Time Complexity of Ldb |
|
|
135 | (4) |
|
6 Pumping: Computational Pigeonholes in Finitary Systems |
|
|
139 | (18) |
|
6.1 Introduction and Synopsis |
|
|
139 | (1) |
|
6.2 Pumping in Algebraic Settings |
|
|
140 | (2) |
|
6.3 Pumping in Regular Languages |
|
|
142 | (8) |
|
6.3.1 Pumping in General Regular Languages |
|
|
143 | (4) |
|
6.3.2 Pumping in Regular Tally Languages |
|
|
147 | (1) |
|
6.3.2.1 A Characterization of the Regular Tally Languages |
|
|
147 | (3) |
|
6.3.2.2 A Purely Combinatorial Characterization |
|
|
150 | (1) |
|
6.4 Pumping in a Robotic Setting: a Mobile FA on a Mesh |
|
|
150 | (7) |
|
6.4.1 The Mesh Mn and Its Subdivisions |
|
|
150 | (3) |
|
6.4.2 The Mobile Finite Automaton (MFA) Model |
|
|
153 | (1) |
|
6.4.3 An Inherent Limitation on Solo Autonomous MEAs |
|
|
153 | (4) |
|
7 Mobility in Computing: An FA Navigates a Mesh |
|
|
157 | (26) |
|
7.1 Introduction and Synopsis |
|
|
157 | (3) |
|
7.2 MEAs That Compute in Read-Only Mode |
|
|
160 | (9) |
|
7.2.1 How an MFA Can Exploit the Structure of Its Host Mesh |
|
|
160 | (1) |
|
7.2.1.1 "Bouncing Off Walls" to Exploit Symmetries |
|
|
160 | (1) |
|
7.2.1.2 Approximating Rational-Slope Paths Within Mn |
|
|
161 | (2) |
|
7.2.2 Solo MFAs Scalably Recognize Non-Regular Languages |
|
|
163 | (1) |
|
7.2.2.1 Matching Forward and Backward Patterns |
|
|
164 | (2) |
|
7.2.2.2 Matching Distinct Forward Patterns |
|
|
166 | (3) |
|
7.3 MFAs as Object-Transporting Robots |
|
|
169 | (14) |
|
7.3.1 Reversing M's Top-Row Pattern to Its Bottom Row |
|
|
170 | (1) |
|
7.3.2 Rotating M's Top-Row Pattern to Its Bottom Row |
|
|
171 | (2) |
|
7.3.3 Algorithms that Circumnavigate M'x "Walls" |
|
|
173 | (3) |
|
7.3.3.1 Sorting-Based Rearrangements |
|
|
176 | (3) |
|
7.3.3.2 Pattern-Checking vs. Pattern Generation |
|
|
179 | (4) |
|
8 The Power of Cooperation: Teams of MFAs on a Mesh |
|
|
183 | (18) |
|
|
|
183 | (3) |
|
8.2 Strictly Coupled MFAs: Parallelism with No Added Power |
|
|
186 | (2) |
|
8.3 Synchronized Computing: A 2-MFA Recognizes {ak bk} |
|
|
188 | (4) |
|
8.4 Queued Computing: MFAs Proceed Through a Pipeline |
|
|
192 | (4) |
|
8.4.1 The "Standard" Form of Pipelining |
|
|
192 | (2) |
|
8.4.2 Streaming a Pipeline/Queue of Agents |
|
|
194 | (2) |
|
8.5 Ushered Computing: Two MFAs Sweep a Mesh-Quadrant |
|
|
196 | (2) |
|
8.6 Sentry-Enabled Computing: MFAs Identify Home Wedges |
|
|
198 | (3) |
|
|
|
201 | (132) |
|
9 Countability and Uncountability: The Precursors of ENCODING |
|
|
203 | (14) |
|
9.1 Encoding Functions and Proofs of Countability |
|
|
206 | (6) |
|
9.2 Diagonalization: Proofs of Uncountability |
|
|
212 | (2) |
|
9.3 Where Has (Un)Countability Led Us? |
|
|
214 | (3) |
|
|
|
217 | (34) |
|
10.1 Introduction and History |
|
|
217 | (6) |
|
10.1.1 Formalizing Mathematical Reasoning |
|
|
217 | (1) |
|
10.1.2 Abstract Computational Models: the Church-Turing Thesis |
|
|
218 | (3) |
|
10.1.3 Thinking About Thinking About Computation |
|
|
221 | (2) |
|
|
|
223 | (5) |
|
10.2.1 Computational Problems as Formal Languages |
|
|
223 | (2) |
|
10.2.2 Functions and Partial Functions |
|
|
225 | (2) |
|
10.2.3 Self-Referential Programs: Interpreters and Compilers |
|
|
227 | (1) |
|
10.3 The Halting Problem: The "Oldest" Unsolvable Problem |
|
|
228 | (6) |
|
10.3.1 The Halting Problem Is Semisolvable but Not Solvable |
|
|
229 | (3) |
|
10.3.2 Why We Care About the Halting Problem--An Example |
|
|
232 | (2) |
|
10.4 Mapping Reducibility |
|
|
234 | (6) |
|
10.4.1 Basic Properties of m-Reducibility |
|
|
236 | (2) |
|
10.4.2 The s-m-n Theorem: An Invaluable Source of Encodings |
|
|
238 | (2) |
|
10.5 The Rice-Myhill-Shapiro Theorem |
|
|
240 | (5) |
|
10.6 Complete--or "Hardest"--Semidecidable Problems |
|
|
245 | (3) |
|
10.7 Some Important Limitations of Computability |
|
|
248 | (3) |
|
11 A Church-Turing Zoo of Computational Models |
|
|
251 | (50) |
|
11.1 The Church-Turing Thesis and Universal Models |
|
|
251 | (2) |
|
11.2 Universality in Simplified OTMs |
|
|
253 | (25) |
|
11.2.1 An OTM with a One-Ended Worktape |
|
|
253 | (3) |
|
11.2.2 An OTM with Two Stacks Instead of a Worktape |
|
|
256 | (4) |
|
11.2.3 An OTM with a FIFO Queue Instead of a Worktape |
|
|
260 | (5) |
|
11.2.4 An OTM with a "Paper" Worktape |
|
|
265 | (4) |
|
11.2.5 An OTM with Registers Instead of a Worktape |
|
|
269 | (7) |
|
11.2.6 A Mobile FA on a Semi-Infinite Mesh |
|
|
276 | (2) |
|
11.3 Enhanced OTMs that Are No More Powerful than OTMs |
|
|
278 | (13) |
|
11.3.1 An OTM Which Has Several Linear Worktapes |
|
|
278 | (5) |
|
11.3.2 An OTM Having Multidimensional Worktapes |
|
|
283 | (4) |
|
11.3.3 An OTM Having a "Random-Access" Worktape |
|
|
287 | (4) |
|
11.4 Models Outside the Classical Mold |
|
|
291 | (8) |
|
11.4.1 Cellular Automata and Kindred Models |
|
|
292 | (1) |
|
11.4.1.1 The Cellular Automaton Model |
|
|
293 | (3) |
|
11.4.1.2 CAs Are Computationally Equivalent to OTMs |
|
|
296 | (1) |
|
11.4.2 TMs as Volunteers; Simulation by Dovetailing |
|
|
297 | (1) |
|
11.4.2.1 Abstract Volunteer Computing (VC) |
|
|
297 | (1) |
|
11.4.2.2 The Abstract VC Model Is Computable |
|
|
298 | (1) |
|
11.5 Learning from the Zoo |
|
|
299 | (2) |
|
12 Pairing Functions as Encoding Mechanisms |
|
|
301 | (32) |
|
12.1 PFs as Storage Mappings for Extendible Arrays/Tables |
|
|
302 | (20) |
|
12.1.1 Insights on PFs via the Cauchy-Cantor Diagonal PF |
|
|
304 | (3) |
|
12.1.2 PFs for Extendible Fixed-Aspect-Ratio Arrays |
|
|
307 | (1) |
|
12.1.2.1 Procedure PF-Constructor |
|
|
307 | (2) |
|
12.1.2.2 A PF for Extendible Square Arrays |
|
|
309 | (1) |
|
12.1.3 The Issue of PF Compactness |
|
|
310 | (1) |
|
12.1.3.1 Inspiration from the PFs We Have Seen Thus Far |
|
|
311 | (1) |
|
12.1.3.2 A PF that Has Minimax-Optimal Spread |
|
|
312 | (3) |
|
12.1.3.3 PFs that Are Designed for a Single Aspect Ratio |
|
|
315 | (1) |
|
12.1.3.4 PFs that Are Designed for a Finite Set of Aspect Ratios |
|
|
315 | (1) |
|
12.1.3.5 The Impact of Bounding Extendibility |
|
|
316 | (5) |
|
12.1.4 Extendible Storage Mappings via Hashing |
|
|
321 | (1) |
|
12.2 Pairing Functions and Volunteer Computing |
|
|
322 | (11) |
|
12.2.1 Basic Questions About Additive PFs |
|
|
324 | (2) |
|
12.2.2 APFs that Have Desirable Computational Properties |
|
|
326 | (1) |
|
12.2.2.1 A Procedure for Designing APFs |
|
|
326 | (2) |
|
12.2.2.2 A Sampler of Explicit Additive PFs |
|
|
328 | (1) |
|
A APFs that stress ease of computation |
|
|
329 | (1) |
|
B APFs that balance efficiency and compactness |
|
|
330 | (1) |
|
C APFs that stress compactness |
|
|
330 | (3) |
|
IV PILLAR R: NONDETERMINISM |
|
|
333 | (112) |
|
13 Nondeterminism as Unbounded Parallelism |
|
|
335 | (8) |
|
13.1 Nondeterministic Online Automata |
|
|
335 | (3) |
|
13.2 A Formal Use of Nondeterminism's Implied Parallelism |
|
|
338 | (2) |
|
13.3 An Overview of Nondeterminism in Computation Theory |
|
|
340 | (3) |
|
14 Nondeterministic Finite Automata |
|
|
343 | (18) |
|
14.1 How Nondeterminism Impacts FA Behavior |
|
|
343 | (5) |
|
14.1.1 NFAs Are No More Powerful than DFAs |
|
|
344 | (2) |
|
14.1.2 Does the Subset Construction Waste DEA States? |
|
|
346 | (2) |
|
14.2 An Application: the Kleene-Myhill Theorem |
|
|
348 | (13) |
|
14.2.1 NFAs with Autonomous Moves |
|
|
348 | (1) |
|
14.2.2 The Kleene-Myhill Theorem |
|
|
349 | (12) |
|
15 Nondeterminism as Unbounded Search |
|
|
361 | (16) |
|
|
|
361 | (1) |
|
15.2 Nondeterministic Turing Machines |
|
|
362 | (9) |
|
|
|
362 | (2) |
|
15.2.2 An Unbounded Search: an OTM Simulates an NTM |
|
|
364 | (7) |
|
15.3 Unbounded Search as Guess-then-Verify |
|
|
371 | (3) |
|
15.4 Unbounded Search as Guess-plus-Verify |
|
|
374 | (3) |
|
15.4.1 Homomorphisms on Formal Languages |
|
|
374 | (1) |
|
15.4.2 Homomorphisms and Regular Languages |
|
|
375 | (2) |
|
|
|
377 | (68) |
|
|
|
377 | (8) |
|
16.2 Time and Space Complexity |
|
|
385 | (14) |
|
16.2.1 On Measuring Time Complexity |
|
|
387 | (1) |
|
16.2.1.1 The Basic Measure of Time Complexity |
|
|
387 | (1) |
|
16.2.1.2 The Classes P and NP |
|
|
388 | (2) |
|
16.2.2 On Measuring Space Complexity |
|
|
390 | (1) |
|
16.2.2.1 The Pointed Palindromes as a Driving Example |
|
|
391 | (7) |
|
16.2.2.2 Space Complexity: Deterministic and Nondeterministic |
|
|
398 | (1) |
|
16.3 Reducibility, Hardness, and Completeness |
|
|
399 | (30) |
|
16.3.1 A General Look at Resource-Bounded Computation |
|
|
400 | (1) |
|
16.3.2 Efficient Mapping Reducibility |
|
|
400 | (6) |
|
16.3.3 Hard Problems; Complete Problems |
|
|
406 | (2) |
|
16.3.4 An NP-Complete Version of the Halting Problem |
|
|
408 | (9) |
|
16.3.5 The Cook-Levin Theorem: The NP-Completeness of SAT |
|
|
417 | (12) |
|
16.4 Nondeterminism and Space Complexity |
|
|
429 | (16) |
|
16.4.1 Simulating Nondeterminism Space-Efficiently |
|
|
431 | (12) |
|
16.4.2 Looking Beyond Savitch's Theorem |
|
|
443 | (2) |
|
V Pillar B: PRESENTATION/SPECIFICATION |
|
|
445 | (46) |
|
17 The Elements of Formal Language Theory |
|
|
447 | (44) |
|
17.1 Early History of Computational Language Research |
|
|
447 | (2) |
|
17.1.1 The Birth of Sophisticated Programming Languages |
|
|
447 | (1) |
|
17.1.1.1 User-Application-Targeted Programming Languages |
|
|
448 | (1) |
|
17.1.1.2 Foundations-Inspired Programming Languages |
|
|
448 | (1) |
|
17.1.1.3 Beyond the Special Purpose and Special Focus |
|
|
448 | (1) |
|
17.2 Elaborating on the Elements of Formal Languages |
|
|
449 | (9) |
|
17.2.1 Language Generation via Formal Grammars |
|
|
450 | (5) |
|
17.2.2 Closure Properties of Interest |
|
|
455 | (3) |
|
17.2.3 Decision Properties of Interest |
|
|
458 | (1) |
|
17.3 Finite Automata and Regular Languages |
|
|
458 | (13) |
|
17.3.1 Mechanisms for Generating Regular Languages |
|
|
458 | (8) |
|
17.3.2 Closure Properties of the Regular Languages |
|
|
466 | (3) |
|
17.3.3 Decision Properties Concerning Regular Languages |
|
|
469 | (2) |
|
17.4 Context-Free Languages: Their Grammars and Automata |
|
|
471 | (20) |
|
17.4.1 Mechanisms for Generating the Context-Free Languages |
|
|
471 | (1) |
|
17.4.1.1 Context-Free Grammars and Normal Forms |
|
|
471 | (1) |
|
17.4.1.2 Pushdown Automata and Their Languages |
|
|
472 | (3) |
|
17.4.1.3 The Chomsky-Evey Theorem: NPDAs and CFLs |
|
|
475 | (4) |
|
17.4.2 Closure Properties of the Context-Free Languages |
|
|
479 | (1) |
|
17.4.2.1 Closure Under the Kleene Operations |
|
|
479 | (3) |
|
17.4.2.2 Pumping in the Context-Free Languages |
|
|
482 | (2) |
|
17.4.2.3 Closure Under the Boolean Operations |
|
|
484 | (2) |
|
17.4.3 Decision Properties of the Context-Free Languages |
|
|
486 | (5) |
|
A A
Chapter-Long Text on Discrete Mathematics |
|
|
491 | (29) |
|
A.1 Sets and Their Operations |
|
|
491 | (5) |
|
|
|
496 | (3) |
|
A.2.1 The Formal Notion of Binary Relation |
|
|
496 | (1) |
|
A.2.2 Equivalence Relations |
|
|
497 | (2) |
|
|
|
499 | (4) |
|
A.3.1 What Is a Function? |
|
|
499 | (2) |
|
A.3.2 Special Categories of Functions |
|
|
501 | (1) |
|
A.3.3 Finite Functions and Pigeonholes |
|
|
502 | (1) |
|
|
|
503 | (4) |
|
A.4.1 The Notion of Language in Computation Theory |
|
|
503 | (2) |
|
A.4.2 Languages as Metaphors for Computational Problems |
|
|
505 | (2) |
|
|
|
507 | (7) |
|
|
|
507 | (2) |
|
A.5.2 Two Recurring Families of Graphs |
|
|
509 | (1) |
|
A.5.2.1 Rooted Directed Trees |
|
|
509 | (2) |
|
A.5.2.2 Mesh-Like Networks |
|
|
511 | (3) |
|
A.6 Useful Quantitative Notions |
|
|
514 | (6) |
|
A.6.1 Two Useful Arithmetic Operations |
|
|
514 | (1) |
|
A.6.2 Asymptotics: Big-O, Big-ω and Big-notation |
|
|
515 | (5) |
|
B Selected Exercises, by
Chapter |
|
|
519 | (1) |
|
B.1 Exercises for Appendix A |
|
|
520 | (1) |
|
B.2 Exercises for
Chapter 2 |
|
|
521 | (1) |
|
B.3 Exercises for
Chapter 3 |
|
|
521 | (5) |
|
B.4 Exercises for
Chapter 4 |
|
|
526 | (1) |
|
B.5 Exercises for
Chapter 5 |
|
|
527 | (1) |
|
B.6 Exercises for
Chapter 6 |
|
|
528 | (1) |
|
B.7 Exercises for
Chapter 7 |
|
|
528 | (1) |
|
B.8 Exercises for
Chapter 8 |
|
|
529 | (1) |
|
B.9 Exercises for
Chapter 9 |
|
|
530 | (1) |
|
B.10 Exercises for
Chapter 10 |
|
|
531 | (1) |
|
B.11 Exercises for
Chapter 11 |
|
|
532 | (1) |
|
B.12 Exercises for
Chapter 12 |
|
|
533 | (1) |
|
B.13 Exercises for
Chapters 13 and 14 |
|
|
534 | (1) |
|
B.14 Exercises for
Chapter 15 |
|
|
535 | (2) |
|
B.15 Exercises for
Chapter 16 |
|
|
537 | (2) |
|
B.16 Exercises for
Chapter 17 |
|
|
539 | (4) |
| List of Acronyms and Symbols |
|
543 | (4) |
| References |
|
547 | (8) |
| Index |
|
555 | |
Lisainfo e-raamatute kohta