An Introduction to the Theory of Computation

Author : Eitan Gurari, Department of Computer Science and Engineering, Ohio State University
ISBN : 0-7167-8182-4
Publication Date : 1989
Publisher : Computer Science Press

Book Excerpts:

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.
- Chapter 2 studies finite-memory programs.
- Chapter 3 considers the introduction of recursion to finite-memory programs.
- Chapter 4 deals with the general class of programs.
- Chapter 5 considers the role of time and space in computations.
- Chapter 6 introduces instructions that allow random choices in programs.
- Chapter 7 is devoted to parallelism.

As a natural outcome, the text also treats the topics of probabilistic and parallel computations. These important topics have matured quite recently, and so far have not been treated in other texts.

The level of the material is intended to provide the reader with introductory tools for understanding and using formal specifications in computer science. As a result, in many cases ideas are stressed more than detailed argumentation, with the objective of developing the reader's intuition toward the subject as much as possible.

Intended Audience:

This book is intended for undergraduate students at advanced stages of their studies, and for graduate students. The reader is assumed to have some experience as a programmer, as well as in handling mathematical concepts. Otherwise no specific prerequisite is necessary.

View/Download An Introduction to the Theory of Computation