Skip to main content
SpringerLink
Log in
Book cover

A Recursive Introduction to the Theory of Computation

  • Textbook
  • © 1994

Overview

Authors:
  1. Carl H. Smith

    1. Department of Computer Science, University of Maryland, College Park, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: Texts in Computer Science (TCS)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 54.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (5 chapters)

  1. Front Matter

    Pages i-viii
    Download chapter PDF

  2. Introduction

    • Carl H. Smith
    Pages 1-2

  3. Models of Computation

    • Carl H. Smith
    Pages 3-30

  4. Basic Recursive Function Theory

    • Carl H. Smith
    Pages 31-67

  5. Abstract Complexity Theory

    • Carl H. Smith
    Pages 68-90

  6. Complete Problems

    • Carl H. Smith
    Pages 91-124

  7. Back Matter

    Pages 125-148
    Download chapter PDF
Back to top

Keywords

About this book

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.

Authors and Affiliations

  • Department of Computer Science, University of Maryland, College Park, USA

    Carl H. Smith

Bibliographic Information

  • Book Title: A Recursive Introduction to the Theory of Computation

  • Authors: Carl H. Smith

  • Series Title: Texts in Computer Science

  • DOI: https://doi.org/10.1007/978-1-4419-8501-9

  • Publisher: Springer New York, NY

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer Science+Business Media New York 1994

  • Hardcover ISBN: 978-0-387-94332-9Published: 14 October 1994

  • Softcover ISBN: 978-1-4612-6420-0Published: 22 November 2012

  • eBook ISBN: 978-1-4419-8501-9Published: 06 December 2012

  • Series ISSN: 1868-0941

  • Series E-ISSN: 1868-095X

  • Edition Number: 1

  • Number of Pages: VIII, 148

  • Topics: Theory of Computation

Publish with us

Policies and ethics

Back to top

Search

Navigation