nach oben

2010 | Buch

Kapitel lesen Erstes Kapitel lesen

The Pillars of Computation Theory

State, Encoding, Nondeterminism

verfasst von: Arnold L. Rosenberg

Verlag: Springer New York

Buchreihe : Universitext

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

PROLEGOMENA

Chapter 1. Introduction

Abstract

This book is intended as an introduction to computation theory for upper-level undergraduate students and lower-level graduate students. We develop the underpinnings of the theory by studying three mathematical concepts that underlie much of the subject, followed by a number of fundamental applications of each concept. This chapter attempts to render concrete the rather abstract philosophical “manifesto” of the preface, focusing specifically on the “three pillars” that give the book its title and that give rise to the “big ideas” that anchor the book.

Arnold L. Rosenberg

Chapter 2. Mathematical Preliminaries

Abstract

This chapter is devoted to reviewing a broad range of mathematical concepts that are central to our approach to developing computation theory. As we develop these concepts, we shall repeatedly observe instances of the following “self-evident truth” (which is what “axiom” means).

Arnold L. Rosenberg

STATE

Chapter 3. Online Automata: Exemplars of “State”

Abstract

An online automaton ¹ (OA, for short) is an abstract device that is a “pure” state-transition system. To hone your intuiton for the formal specification of OAs, consider Figure 3.1, which depicts a finite OA²—which we shall later (in the next chapter, in fact) call a finite automaton (FA, for short and finite automata in the plural). One can think about an OA M as a simple machine that communicates with the world via

Arnold L. Rosenberg

Chapter 4. Finite Automata and Regular Languages

Abstract

A finite automaton (FA, for short) is an online automaton whose state-set Q is finite. The finite automaton model amply illustrates the three features of computation theory described in Chapter 1. Essentially equivalent models of finite-state systems were developed over a span of three decades, to model a large range of “real-life” systems. In roughly chronological order

Arnold L. Rosenberg

Chapter 5. Applications of the Myhill–Nerode Theorem

Abstract

This chapter is devoted to justifying our praise for the Myhill–Nerode theorem, by developing a few of its applications. We strive to display both the usefulness of the theorem and its versatility.

Arnold L. Rosenberg

Chapter 6. Enrichment Topics

Abstract

This section is devoted to discussing a phenomenon called “pumping,” which is a characteristic of any finite closed mathematical system. We introduce this notion in order to explain the so-called pumping lemma for regular languages (and, briefly, its analogue for so-called context-free languages). Most textbooks introduce the pumping lemma as the primary tool for exposing the limitations of FAs. The reader will see from the discussion throughout this section that we disagree with this point of view, on both conceptual and methodological grounds. We hope that the reader will agree with us after reading this section’s rather thorough explanation of the pumping lemma, its origins, its strengths, and its weaknesses.

Arnold L. Rosenberg

ENCODING

Chapter 7. Countability and Uncountability: The Precursors of “Encoding”

Abstract

The theory of countability (and uncountability) began with Georg Cantor’s deliberations on the nature of infinity [10]. Cantor concentrated on questions that can be framed intuitively as follows: Are there “more” rational numbers than integers? Are there “more” real numbers than integers? (Note that we need to put “more” in quotes, because all three sets, the integers, the rational numbers, and the real numbers, are infinite—so what does “more” mean?)

Arnold L. Rosenberg

Chapter 8. Enrichment Topic: “Efficient” Pairing Functions, with Applications

Abstract

We have already seen the preceding admonition by William of Occam (fourteenthth century), in Section 6.1.2. The principle that underlies the admonition—always to strive for simplicity—is particularly worth heeding when one seeks mathematical models of computational phenomena, for it is always tempting to embellish one’s models with “real” features of the phenomenon or structure being modeled.

Arnold L. Rosenberg

Chapter 9. Computability Theory

Abstract

Mathematics has been “practiced” for thousands of years, yet it was not until the nineteenth century that people began to attempt to crystalize/formalize the notion of proof.

Arnold L. Rosenberg

NONDETERMINISM

Chapter 10. Nondeterministic Online Automata

Abstract

We saw in Section 3.1 that one can view OAs as abstract representations of actual circuits or machines or programs. In contrast, the generalization of OAs that we present now is a mathematical abstraction that cannot be realized directly from conventional hardware or software elements. It is best to view this model either as a pure mathematical convenience—whose utility we shall see imminently—or as a “computational strategy” that we shall try to realize via sophisticated transformation of a program.

Arnold L. Rosenberg

Chapter 11. Nondeterministic FAs

Abstract

The material in this section refines the development in Chapter 10 by restricting attention to NOAs whose set Q of states is finite. We call such an NOA a nondeterministic finite automaton (NFA, for short).

Arnold L. Rosenberg

Chapter 12. Nondeterminism in Computability Theory

Abstract

We begin our study of nondeterminism in computability theory by crafting a nondeterministic version of the online Turing machine (OTM) of Section 3.3; we call this enhanced model an NTM, for “nondeterministic Turing machine.” The NTM model provides us a “bookend” to match our study of nondeterministic finite automata (NFAs) in Chapter 11. Whereas NFAs arise from adding nondeterminism to the computationally weakest model in our study, namely FAs, NTMs arise from adding nondeterminism to the computationally most powerful model in our study—indeed, the computationally most powerful possible model, period, according to the Church–Turing thesis.

Arnold L. Rosenberg

Chapter 13. Complexity Theory

Abstract

Perhaps the major—certainly the most dramatic—strength of computability theory is its robustness across widely varying models, as expressed in the Church-Turing thesis. Probably the major weaknesses of computability theory are

Arnold L. Rosenberg

Backmatter

Titel: The Pillars of Computation Theory
verfasst von: Arnold L. Rosenberg
Verlag: Springer New York
Electronic ISBN: 978-0-387-09639-1
Print ISBN: 978-0-387-09638-4
DOI: https://doi.org/10.1007/978-0-387-09639-1