The pillars of computation theory. State, encoding, nondeterminism (Q1039511)

The abstract branch of theoretical computer science known as Computation Theory typically appears in undergraduate academic curricula in a form that obscures both the mathematical concepts that are central to the various components of the theory and the relevance of the theory to the typical student. This regrettable situation is due largely to the thematic tension among three main competing principles for organizing the material in the course. This book is motivated by the belief that a deep understanding of, and operational control over, the few ``big'' mathematical ideas that underlie Computation Theory is the best way to enable the typical student to assimilate the ``big ideas'' of Computation Theory into her daily computational life. The author charts a path by teaching the major themes that underlie all of computer science. He identifies three themes, or pillars: `state', `encoding', and `nondeterminism', which are the main ingredients of computer science in general, and, in particular, of computation theory. The author builds the elements of computation theory upon these three pillars: Chapters 3--6 are devoted to the first pillar, ``State'', Chapters 7--9 are devoted to the part ``Encoding'', and Chapters 10--13 are devoted to the part ``Nondeterminism''. Chapters 1 and 2 consist of the Introduction and the mathematical preliminaries. The author's approach singles out certain concepts and results of the three classical branches of computation theory as ``big ideas'' and, as is indicated in the author's preface, the author views this as a strength of the approach: he does go beyond these ``big ideas'' as he develops the material, so that the ``big ideas'' emerge as major signposts in a rich landscape rather than as a collection of isolated topics. In the part ``State'', the author introduces a formal model that he calls an \textit{online automaton}, which is a very abstract computational model that allows to isolate the notion of ``state''. The conceptional pinnacle of this part is the famous Myhill-Nerode theorem, which is developed in this book in two versions, a weak version for online automata and a strong one for finite automata. The remainder of this part focuses on several applications of this theorem. The part is closed with a brief development of so-called pumping lemmas for two classes of languages. The part ``Encoding'' contains the following three chapters: Chapter 7. Countability and uncountability: the precursors of ``Encoding''. Chapter 8. Enrichment topic: ``efficient'' pairing functions, with applications. Chapter 9. Computability theory. This last chapter contains examples of the not solvable and semisolvable problems (an example is the halting problem), a brief study of the many-one reducibility and the s-m-n and Rice-Myhill-Shapiro theorems, and a study of the completely undecidable problems. The chapter closes with a discussion of the Church-Turing Thesis, using the online automata, which allows to give the reader some intuition for why people accept the Church-Turing Thesis as a working hypothesis. The last part, ``Nondeterminism'', contains four chapters whose titles give appropriate information on their contents. Chapter 10. Nondeterministic online automata. Chapter 11. Nondeterministic FAs. Chapter 12. Nondeterminism in computability theory. This chapter contains two paragraphs: Nondeterministic Turing machines; and Nondeterminism as unbounded search. Chapter 13. Complexity theory. This chapter contains three paragraphs: Time and space complexity; Reducibility, hardness, and completeness in complexity theory; and Nondeterminism and space complexity.