Understanding Computation: Pillars, Paradigms, Principles

Preface.- I: Introduction.- 1 Introducing Computation Theory.- 2 Introducing the Book.- II: Pillar S: STATE.- 3 Pure State-Based Computational Models.- 4 The Myhill-Nerode Theorem: Implications and Applications.- 5 Online Turing Machines and the Implications of Online Computing.- 6 Pumping: Computational Pigeonholes in Finitary Systems.- 7 Mobility in Computing: An FA Navigates a Mesh.- 8 The Power of Cooperation: Teams of MFAs on a Mesh.- III: Pillar E: ENCODING.- 9 Countability and Uncountability: The Precursors of ENCODING.- 10 Computability Theory.- 11 A Church-Turing Zoo of Computational Models.- 12 Pairing Functions as Encoding Mechanisms.- IV: Pillar N: NONDETERMINISM.- 13 Nondeterminism as Unbounded Parallelism.- 14 Nondeterministic Finite Automata.- 15 Nondeterminism as Unbounded Search.- 16 Complexity Theory.- V: Pillar P: PRESENTATION/SPECIFICATION.- 17 The Elements of Formal Language Theory.- A A Chapter-Long Text on Discrete Mathematics.- B Selected Exercises, by Chapter.- List of ACRONYMS and SYMBOLS.- References.- Index.

前言。- I: 簡介。- 1.引入計算理論。- 2.介紹本書。- II: S支柱: 狀態。- 3.純狀態計算模型。- 4.Myhill-Nerode定理: 影響和應用。- 5.在線圖靈機和在線計算的影響。- 6.泵引: 有限系統中的計算鴿洞。- 7.計算中的移動性: 一個有限自動機在網格上導航。- 8.合作的力量: 一個網格上的多有限自動機團隊。- III: E支柱: 編碼。- 9.可數性和不可數性: 編碼的前身。- 10.可計算性理論。- 11.計算模型的Church-Turing動物園。- 12.配對函數作為編碼機制。- IV: N支柱: 非確定性。- 13.非確定性作為無界並行。- 14.非確定有限自動機。- 15.非確定性作為無界搜索。- 16.複雜性理論。- V: P支柱: 表示/規範。- 17.形式語言理論的要素。- A.一章長的離散數學文本。- B.按章節選擇的練習題。- 首字母縮寫和符號列表。- 參考文獻。- 索引。