Computability, Complexity, and Languages

Computability, Complexity, and Languages

Fundamentals of Theoretical Computer Science

1st Edition - December 1, 1983

Write a review

  • Authors: Martin D. Davis, Elaine J. Weyuker
  • eBook ISBN: 9781483264585

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order


Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science provides an introduction to the various aspects of theoretical computer science. Theoretical computer science is the mathematical study of models of computation. This text is composed of five parts encompassing 17 chapters, and begins with an introduction to the use of proofs in mathematics and the development of computability theory in the context of an extremely simple abstract programming language. The succeeding parts demonstrate the performance of abstract programming language using a macro expansion technique, along with presentations of the regular and context-free languages. Other parts deal with the aspects of logic that are important for computer science and the important theory of computational complexity, as well as the theory of NP-completeness. The closing part introduces the advanced recursion and polynomial-time computability theories, including the priority constructions for recursively enumerable Turing degrees. This book is intended primarily for undergraduate and graduate mathematics students.

Table of Contents

  • Preface


    Dependency Graph

    Chapter 1 Preliminaries

    1. Sets and n-Tuples

    2. Functions

    3. Alphabets and Strings

    4. Predicates

    5. Quantifiers

    6. Proof by Contradiction

    7. Mathematical Induction

    Part 1 Computability

    Chapter 2 Programs and Computable Functions

    1. A Programming Language

    2. Some Examples of Programs

    3. Syntax

    4. Computable Functions

    5. More About Macros

    Chapter 3 Primitive Recursive Functions

    1. Composition

    2. Recursion

    3. PRC Classes

    4. Some Primitive Recursive Functions

    5. Primitive Recursive Predicates

    6. Iterated Operations and Bounded Quantifiers

    7. Minimalization

    8. Pairing Functions and Gödel Numbers

    Chapter 4 A Universal Program

    1. Coding Programs by Numbers

    2. The Halting Problem

    3. Universality

    4. Recursively Enumerable Sets

    5. The Parameter Theorem

    6. The Recursion Theorem

    7. Rice's Theorem 67

    Chapter 5 Calculations on Strings

    1. Numerical Representation of Strings

    2. A Programming Language for String Computations

    3. The Languages ℓ and ℓn

    4. Post-Turing Programs

    5. Simulation of ℓ in T

    6. Simulation of T in ℓ

    Chapter 6 Turing Machines

    1. Internal States

    2. A Universal Turing Machine

    3. The Languages Accepted by Turing Machines

    4. The Halting Problem for Turing Machines

    5. Nondeterministic Turing Machines

    6. Variations on the Turing Machine Theme

    Chapter 7 Processes and Grammars

    1. Semi-Thue Processes

    2. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes

    3. Unsolvable Word Problems

    4. Post's Correspondence Problem

    5. Grammars

    6. Some Unsolvable Problems Concerning Grammars

    7. Recursion and Minimalization

    8. Normal Processes

    9. A Non-R.E. Set

    Part 2 Grammars and Automata

    Chapter 8 Regular Languages

    1. Finite Automata

    2. Nondeterministic Finite Automata

    3. Additional Examples

    4. Closure Properties

    5. Kleene's Theorem

    6. The Pumping Lemma and Its Applications

    7. The Myhill-Nerode Theorem

    Chapter 9 Context-Free Languages

    1. Context-Free Grammars and Their Derivation Trees

    2. Regular Grammars

    3. Chomsky Normal Form

    4. Bar-Hillers Pumping Lemma

    5. Closure Properties

    6. Solvable and Unsolvable Problems

    7. Bracket Languages

    8. Pushdown Automata

    9. Compilers and Formal Languages

    Chapter 10 Context-Sensitive Languages

    1. The Chomsky Hierarchy

    2. Linear Bounded Automata

    3. Closure Properties

    Part 3 Logic

    Chapter 11 Propositional Calculus

    1. Formulas and Assignments

    2. Tautological Inference

    3. Normal Forms

    4. The Davis-Putnam Rules

    5. Minimal Unsatisfiability and Subsumption

    6. Resolution

    7. The Compactness Theorem

    Chapter 12 Quantification Theory

    1. The Language of Predicate Logic

    2. Semantics

    3. Logical Consequence

    4. Herbrand's Theorem

    5. Unification

    6. Compactness and Countability

    7. Gödel's Incompleteness Theorem

    8. Unsolvability of the Satisfiability Problem in Predicate Logic

    Part 4 Complexity

    Chapter 13 Loop Programs

    1. The Language L and Primitive Recursive Functions

    2. Running Time

    3. ℓn as a Hierarchy

    4. A Converse to the Bounding Theorem

    5. Doing without Branch Instructions

    Chapter 14 Abstract Complexity

    1. The Blum Axioms

    2. The Gap Theorem

    3. Preliminary Form of the Speedup Theorem

    4. The Speedup Theorem Concluded

    Chapter 15 Polynomial-Time Computability

    1. Rates of Growth

    2. P Versus NP

    3. Cook's Theorem

    4. Other NP-Complete Problems

    Part 5 Unsolvability

    Chapter 16 Classifying Unsolvable Problems

    1. Using Oracles

    2. Relativization of Universality

    3. Reducibility

    4. Sets R.E. Relative to an Oracle

    5. The Arithmetic Hierarchy

    6. Post's Theorem

    7. Classifying Some Unsolvable Problems

    8. Rice's Theorem Revisited

    9. Recursive Permutations

    Chapter 17 Degrees of Unsolvability and Post's Problem

    1. Turing Degrees

    2. The Kleene-Post Theorem

    3. Creative Sets—Myhill's Theorem

    4. Simple Sets—Dekker's Theorem

    5. Sacks's Splitting Theorem

    6. The Priority Method

    Suggestions for Further Reading


Product details

  • No. of pages: 446
  • Language: English
  • Copyright: © Academic Press 1983
  • Published: December 1, 1983
  • Imprint: Academic Press
  • eBook ISBN: 9781483264585

About the Authors

Martin D. Davis

Elaine J. Weyuker

About the Editor

Werner Rheinboldt

Ratings and Reviews

Write a review

There are currently no reviews for "Computability, Complexity, and Languages"