Intro
Contents
Preface
Part I INTRODUCTION
Chapter 1 Introducing Computation Theory
1.1 The Autobiographical (ALR) Seeds of Our Framework
1.1.1 Computation by "Shapeless" Agents and Devices
1.1.2 Computation Theory as a Study of Computation
1.2 The Highlights of Our Framework: How We Tell the Story
1.3 Why Is a New Computation Theory Text Needed?
Chapter 2 Introducing the Book
2.1 Computation Theory as a Branch of Discrete Mathematics
2.1.1 Dynamism Within Traditional Mathematics
2.1.2 Discrete Mathematics with Computational Objects

2.2 The Four Pillars of Computation Theory
2.2.1 Pillar S: STATE
2.2.2 Pillar E: ENCODING
2.2.3 Pillar N: NONDETERMINISM
2.2.4 Pillar P: PRESENTATION/SPECIFICATION
2.2.5 Summing Up
2.3 A Map of the Book by Chapter
2.4 Ways of Using this Book
2.4.1 As a Text for a "Classical" Theory Course
2.4.2 As a Primary Text: "Big Ideas in Computation"
2.4.3 As a Supplemental Text: "Theoretical Aspects of-"
2.5 Tools for Using the Book
Part II Pillar S: STATE
Chapter 3 Pure State-Based Computational Models
3.1 Online Automata and Their Languages

3.1.1 Basics of the OA Model
3.1.2 Preparing to Understand the Notion State
3.1.3 A Myhill-Nerode-like Theorem for OAs
3.2 Finite Automata and Regular Languages
3.2.1 Overview and History
3.2.2 Perspectives on Finite Automata
3.2.3 Why FAs Get Confused: a Consequence of Finiteness
Chapter 4 The Myhill-Nerode Theorem: Implications and Applications
4.1 The Myhill-Nerode Theorem for FAs
4.1.1 The Theorem: States Are Equivalence Classes
4.1.2 What Do ≡L- Equivalence Classes Look Like?
4.2 Sample Applications of the Myhill-Nerode Theorem

4.2.1 Proving that Languages Are Not Regular
4.2.2 On Minimizing Finite Automata
4.2.3 Two-Way (Offline) Finite Automata
4.2.4 ⊕ Finite Automata with Probabilistic Transitions
4.2.5 ⊕ State as a Memory-Constraining Resource
Chapter 5 Online Turing Machines and the Implications of Online Computing
5.1 Online Turing Machines: Realizations of Infinite OAs
5.1.1 OTMs with Abstract Storage Devices
5.1.2 OTMs with Linear Tapes for Storage
5.2 The Nature of Online Computing
5.2.1 Online TMs with Multiple Complex Tapes
5.2.2 An Information-Retrieval Problem as a Language

5.2.3 The Impact of Tape Structure on Memory Locality
5.2.4 Tape Dimensionality and the Time Complexity of LDB
Chapter 6 Pumping: Computational Pigeonholes in Finitary Systems
6.1 Introduction and Synopsis
6.2 Pumping in Algebraic Settings
6.3 Pumping in Regular Languages
6.3.1 Pumping in General Regular Languages
6.3.2 Pumping in Regular Tally Languages
6.4 Pumping in a Robotic Setting: a Mobile FA on a Mesh
6.4.1 The Mesh Mn and Its Subdivisions
6.4.2 The Mobile Finite Automaton (MFA) Model
6.4.3 An Inherent Limitation on Solo Autonomous MFAs