A Recursive Introduction to the Theory of Computation

Description

The aim of this textbook is to present an account of the theory of computation. After introducing the concept of a model of computation and presenting various examples, the author explores the limitations of effective computation via basic recursion theory. Self-reference and other methods are introduced as fundamental and basic tools for constructing and manipulating algorithms. From there the book considers the complexity of computations and the notion of a complexity measure is introduced. Finally, the book culminates in considering time and space measures and in classifying computable functions as being either feasible or not. The author assumes only a basic familiarity with discrete mathematics and computing, making this textbook ideal for a graduate-level introductory course. It is based on many such courses presented by the author and so numerous exercises are included. In addition, the solutions to most of these exercises are provided. Cover......Page __sk_0000.djvu Copyright......Page __sk_0002.djvu Contents......Page __sk_0005.djvu Preface......Page __sk_0003.djvu Introduction......Page __sk_0007.djvu 1. Models of Computation......Page __sk_0009.djvu 1.1 Random Access Machines......Page __sk_0010.djvu 1.2 Partial Recursive Functions......Page __sk_0013.djvu 1.3 Pairing and Coding......Page __sk_0022.djvu 1.4 Simulating an Execution of a RAM Program......Page __sk_0026.djvu 1.5 Turing Machines......Page __sk_0028.djvu 1.6 Some Other Models......Page __sk_0032.djvu 1.7 A Representation for Programs......Page __sk_0034.djvu 1.8 Historical Notes......Page __sk_0036.djvu 2.1 Acceptable Programming Systems......Page __sk_0037.djvu 2.2 Recursion Theorems......Page __sk_0042.djvu 2.3 Alternative Characterizations......Page __sk_0054.djvu 2.4 The Isomorphism Theorem......Page __sk_0058.djvu 2.5 Algorithmically Unsolvable Problems......Page __sk_0060.djvu 2.6 Recursively Enumerable Sets......Page __sk_0064.djvu 2.7 Historical Notes......Page __sk_0073.djvu 3. Abstract Complexity Theory......Page __sk_0074.djvu 3.1 RAM Pseudospace Measure......Page __sk_0075.djvu 3.2 Abstract Complexity Measures......Page __sk_0076.djvu 3.3 Fundamental Results......Page __sk_0080.djvu 3.4 Complexity Gaps......Page __sk_0083.djvu 3.5 Complexity Compression......Page __sk_0085.djvu 3.6 Speed-up......Page __sk_0086.djvu 3.7 Measures of Program Size......Page __sk_0090.djvu 3.8 Restricted Programming Systems......Page __sk_0094.djvu 3.9 Historical Notes......Page __sk_0096.djvu 4.1 Reducibilities......Page __sk_0097.djvu 4.2 Polynomial Computability......Page __sk_0100.djvu 4.3 The Deterministic Time Hierarchy......Page __sk_0101.djvu 4.4 Nondeterminism......Page __sk_0109.djvu 4.5 An NP-Complete Problem......Page __sk_0115.djvu 4.6 More NP-Complete Problems......Page __sk_0122.djvu 4.7 Historical Notes......Page __sk_0130.djvu Solutions to Selected Exercises......Page __sk_0131.djvu List of Symbols......Page __sk_0148.djvu Index......Page __sk_0150.djvu