## A Recursive Introduction to the Theory of ComputationThe 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 |

142 | |

144 | |

### Other editions - View all

### Common terms and phrases

acceptable programming system algorithm arguments block Boolean expression bounded canceled clique CNFSAT complexity measure configuration conjunctive normal form consider construct contradiction defined Definition denote diagonalization DIRECTED HAMILTONIAN CIRCUIT domain DTIME(T2 effectively encode example executed Exercise exists finite set fixed point theorem formal function f given graph halting problem Hence implicit increment index set induction infinite input instantaneous description ith instruction Justify your answer Lemma lower track model of computation monotone natural numbers nondeterministic nondeterministic Turing machine NP-Complete otherwise output pairs partial recursive functions pe(x pe+i polynomial primitive recursive functions proof pseudospace quintuples r.e. sets RAM computable functions RAM program range recursion theorem recursive set register Ri result s-m-n theorem self-referential sequence simulate space stage steps string symbols tape techniques tion true iff Turing machine undefined universal programming system variables vertex cover vertices