An Introduction to the Theory of Computation

This book explores 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.

**Tag(s):**
Theory of Computation

**Publication date**: 31 Dec 1989

**ISBN-10**:
0716781824

**ISBN-13**:
n/a

**Paperback**:
600 pages

**Views**: 56,269

An Introduction to the Theory of Computation

This book explores 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.

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.

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.

Tweet

About The Author(s)

Dr. Gurari was born in Israel in March 1947. He attended Technion - Israel Institute of Technology where, in 1971, he received Bachelors of Science in Physics. He continued his studies there, but changed focus to Computer Science receiving a Masters degree in 1974. The University of Minnesota granted him a Ph.D. in 1978 (Computer Science) after which he taught at the University of Wisconsin - Milwaukee and the State University of New York at Buffalo. He joined the Ohio State University Department of Computer Science and Engineering in 1982.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Rexx
Microsoft .NET
Perl
PHP
R
Python
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors