A Recursive Introduction to the Theory of Computation

Front Cover
Springer Science & Business Media, Oct 14, 1994 - Computers - 148 pages
0 Reviews
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Models of Computation
3
11 Random Access Machines
4
12 Partial Recursive Functions
7
13 Pairing and Coding
16
14 Simulating an Execution of a RAM Program
20
15 Turing Machines
22
16 Some Other Models
26
17 A Representation for Programs
28
33 Fundamental Results
74
34 Complexity Gaps
77
35 Complexity Compression
79
36 Speedup
80
37 Measures of Program Size
84
38 Restricted Programming Systems
88
39 Historical Notes
90
Complete Problems
91

18 Historical Notes
30
Basic Recursive Function Theory
31
22 Recursion Theorems
36
23 Alternative Characterizations
48
24 The Isomorphism Theorem
52
25 Algorithmically Unsolvable Problems
54
26 Recursively Enumerable Sets
58
27 Historical Notes
67
Abstract Complexity Theory
68
31 RAM Pseudospace Measure
69
32 Abstract Complexity Measures
70
42 Polynomial Computability
94
43 The Deterministic Time Hierarchy
95
44 Nondeterminism
103
45 An NPComplete Problem
109
46 More NPComplete Problems
116
47 Historical Notes
124
Solutions to Selected Exercises
125
List of Symbols
142
Index
144
Copyright

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »

Bibliographic information