theory-bk.html
An Introduction to the Theory of
Computation
Eitan Gurari, Ohio State University
Computer Science Press, 1989, ISBN 0-7167-8182-4
Copyright © Eitan M. Gurari
To Shaula, Inbal, Itai, Erez, Netta, and Danna
Preface
1
GENERAL CONCEPTS
1.1
Alphabets, Strings, and Representations
1.2
Formal Languages and Grammars
1.3
Programs
1.4
Problems
1.5
Reducibility among Problems
Exercises
Bibliographic Notes
2
FINITE-MEMORY PROGRAMS
2.1
Motivation
2.2
Finite-State Transducers
2.3
Finite-State Automata and Regular Languages
2.4
Limitations of Finite-Memory Programs
2.5
Closure Properties for Finite-Memory Programs
2.6
Decidable Properties for Finite-Memory Programs
Exercises
Bibliographic Notes
3
RECURSIVE FINITE-DOMAIN PROGRAMS
3.1
Recursion
3.2
Pushdown Transducers
3.3
Context-Free Languages
3.4
Limitations of Recursive Finite-Domain Programs
3.5
Closure Properties for Recursive Finite-Domain Programs
3.6
Decidable Properties for Recursive Finite-Domain Programs
Exercises
http://www.cis.ohio-state.edu/~gurari/theory-bk/theory-bk.html (1 of 3) [2/24/2003 1:46:54 PM]
theory-bk.html
Bibliographic Notes
4
GENERAL PROGRAMS
4.1
Turing Transducers
4.2
Programs and Turing Transducers
4.3
Nondeterminism versus Determinism
4.4
Universal Turing Transducers
4.5
Undecidability
4.6
Turing Machines and Type 0 Languages
4.7
Post's Correspondence Problem
Exercises
Bibliographic Notes
5
RESOURCE-BOUNDED COMPUTATION
5.1
Time and Space
5.2
A Time Hierarchy
5.3
Nondeterministic Polynomial Time
5.4
More NP-Complete Problems
5.5
Polynomial Space
5.6
P-Complete Problems
Exercises
Bibliographic Notes
6
PROBABILISTIC COMPUTATION
6.1
Error-Free Probabilistic Programs
6.2
Probabilistic Programs That Might Err
6.3
Probabilistic Turing Transducers
6.4
Probabilistic Polynomial Time
Exercises
Bibliographic Notes
7
PARALLEL COMPUTATION
7.1
Parallel Programs
7.2
Parallel Random Access Machines
7.3
Circuits
7.4
Uniform Families of Circuits
7.5
Uniform Families of Circuits and Sequential Computations
7.6
Uniform Families of Circuits and PRAM's
Exercises
Bibliographic Notes
A
MATHEMATICAL NOTIONS
A.1
Sets, Relations, and Functions
http://www.cis.ohio-state.edu/~gurari/theory-bk/theory-bk.html (2 of 3) [2/24/2003 1:46:54 PM]
theory-bk-preface.html
[next] [tail] [up]
Preface
Computations are designed to solve problems. Programs are descriptions of computations written for
execution on computers. The field of computer science is concerned with the development of
methodologies for designing programs, and with the development of computers for executing programs.
It is therefore of central importance for those involved in the field that the characteristics of programs,
computers, problems, and computation be fully understood. Moreover, to clearly and accurately
communicate intuitive thoughts about these subjects, a precise and well-defined terminology is required.
This book explores some of the more important terminologies and questions concerning programs,
computers, problems, and computation. The exploration reduces in many cases to a study of
mathematical theories, such as those of automata and formal languages; theories that are interesting also
in their own right. These theories provide abstract models that are easier to explore, because their
formalisms avoid irrelevant details.
Organized into seven chapters, the material in this book gradually increases in complexity. In many
cases, new topics are treated as refinements of old ones, and their study is motivated through their
association to programs.
Chapter 1 is concerned with the definition of some basic concepts. It starts by considering the notion of
strings, and the role that strings have in presenting information. Then it relates the concept of languages
to the notion of strings, and introduces grammars for characterizing languages. The chapter continues by
introducing a class of programs. The choice is made for a class, which on one hand is general enough to
model all programs, and on the other hand is primitive enough to simplify the specific investigation of
programs. In particular, the notion of nondeterminism is introduced through programs. The chapter
concludes by considering the notion of problems, the relationship between problems and programs, and
some other related notions.
Chapter 2 studies finite-memory programs. The notion of a state is introduced as an abstraction for a
location in a finite-memory program as well as an assignment to the variables of the program. The notion
of state is used to show how finite-memory programs can be modeled by abstract computing machines,
called finite-state transducers. The transducers are essentially sets of states with rules for transition
between the states. The inputs that can be recognized by finite-memory programs are characterized in
terms of a class of grammars, called regular grammars. The limitations of finite-memory programs,
closure properties for simplifying the job of writing finite-memory programs, and decidable properties of
such programs are also studied.
Chapter 3 considers the introduction of recursion to finite-memory programs. The treatment of the new
programs, called recursive finite-domain programs, resembles that for finite-memory programs in
http://www.cis.ohio-state.edu/~gurari/theory-bk/theory-bk-preface.html (1 of 4) [2/24/2003 1:46:56 PM]
theory-bk-preface.html
Chapter 2. Specifically, the recursive finite-domain programs are modeled by abstract computing
machines, called pushdown transducers. Each pushdown transducer is essentially a finite-state transducer
that can access an auxiliary memory that behaves like a pushdown storage of unlimited size. The inputs
that can be recognized by recursive finite-domain programs are characterized in terms of a generalization
of regular grammars, called context-free grammars. Finally, limitations, closure properties, and decidable
properties of recursive finite-domain programs are derived using techniques similar to those for finite-
memory programs.
Chapter 4 deals with the general class of programs. Abstract computing machines, called Turing
transducers, are introduced as generalizations of pushdown transducers that place no restriction on the
auxiliary memory. The Turing transducers are proposed for characterizing the programs in general, and
computability in particular. It is shown that a function is computable by a Turing transducer if and only if
it is computable by a deterministic Turing transducer. In addition, it is shown that there exists a universal
Turing transducer that can simulate any given deterministic Turing transducer. The limitations of Turing
transducers are studied, and they are used to demonstrate some undecidable problems. A grammatical
characterization for the inputs that Turing transducers recognize is also offered.
Chapter 5 considers the role of time and space in computations. It shows that problems can be classified
into an infinite hierarchy according to their time requirements. It discusses the feasibility of those
computations that can be carried out in "polynomial time" and the infeasibility of those computations that
require "exponential time." Then it considers the role of "nondeterministic polynomial time." "Easiest"
hard problems are identified, and their usefulness for detecting hard problems is exhibited. Finally, the
relationship between time and space is examined.
Chapter 6 introduces instructions that allow random choices in programs. Deterministic programs with
such instructions are called probabilistic programs. The usefulness of these programs is considered, and
then probabilistic Turing transducers are introduced as abstractions of such programs. Finally, some
interesting classes of problems that are solvable probabilistically in polynomial time are studied.
Chapter 7 is devoted to parallelism. It starts by considering parallel programs in which the
communication cost is ignored. Then it introduces "high-level" abstractions for parallel programs, called
PRAM's, which take into account the cost of communication. It continues by offering a class of
"hardware-level" abstractions, called uniform families of circuits, which allow for a rigorous analysis of
the complexity of parallel computations. The relationship between the two classes of abstractions is
detailed, and the applicability of parallelism in speeding up sequential computations is considered.
The motivation for adding this text to the many already in the field originated from the desire to provide
an approach that would be more appealing to readers with a background in programming. A unified
treatment of the subject is therefore provided, which links the development of the mathematical theories
to the study of programs.
The only cost of this approach occurs in the introduction of transducers, instead of restricting the
http://www.cis.ohio-state.edu/~gurari/theory-bk/theory-bk-preface.html (2 of 4) [2/24/2003 1:46:56 PM]
