Research Catalog
A recursive introduction to the theory of computation
- Title
- A recursive introduction to the theory of computation / Carl Smith.
- Author
- Smith, Carl, 1950-
- Publication
- New York : Springer-Verlag, 1994.
Items in the Library & Off-site
Filter by
1 Item
| Status | Format | Access | Call Number | Item Location |
|---|---|---|---|---|
| Text | Request in advance | QA76.6 .S61547 1994 | Off-site |
Details
- Description
- viii, 148 pages : illustrations; 25 cm.
- Series Statement
- Graduate texts in computer science
- Uniform Title
- Graduate texts in computer science.
- Subjects
- Bibliography (note)
- Includes bibliographical references and index.
- Contents
- 1. Models of Computation. 1.1. Random Access Machines. 1.2. Partial Recursive Functions. 1.3. Pairing and Coding. 1.4. Simulating an Execution of a RAM Program. 1.5. Turing Machines. 1.6. Some Other Models. 1.7. A Representation for Programs -- 2. Basic Recursive Function Theory. 2.1. Acceptable Programming Systems. 2.2. Recursion Theorems. 2.3. Alternative Characterizations. 2.4. The Isomorphism Theorem. 2.5. Algorithmically Unsolvable Problems. 2.6. Recursively Enumerable Sets -- 3. Abstract Complexity Theory. 3.1. RAM Pseudospace Measure. 3.2. Abstract Complexity Measures. 3.3. Fundamental Results. 3.4. Complexity Gaps. 3.5. Complexity Compression. 3.6. Speed-up. 3.7. Measures of Program Size. 3.8. Restricted Programming Systems -- 4. Complete Problems. 4.1. Reducibilities. 4.2. Polynomial Computability. 4.3. The Deterministic Time Hierarchy. 4.4. Nondeterminism. 4.5. An NP-Complete Problem. 4.6. More NP-Complete Problems.
- ISBN
- 0387943323 (acid-free paper)
- LCCN
- 94021785
- OCLC
- 30594165
- ocm30594165
- Owning Institutions
- Columbia University Libraries