Computability Theory - 1st Edition - ISBN: 9780123900500, 9781483218489

Computability Theory

1st Edition

An Introduction

Authors: Neil D. Jones
Editors: Robert L. Ashenhurst
eBook ISBN: 9781483218489
Imprint: Academic Press
Published Date: 28th January 1973
Page Count: 168
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


Computability Theory: An Introduction provides information pertinent to the major concepts, constructions, and theorems of the elementary theory of computability of recursive functions. This book provides mathematical evidence for the validity of the Church–Turing thesis. Organized into six chapters, this book begins with an overview of the concept of effective process so that a clear understanding of the effective computability of partial and total functions is obtained. This text then introduces a formal development of the equivalence of Turing machine computability, enumerability, and decidability with other formulations. Other chapters consider the formulas of the predicate calculus, systems of recursion equations, and Post's production systems. This book discusses as well the fundamental properties of the partial recursive functions and the recursively enumerable sets. The final chapter deals with different formulations of the basic ideas of computability that are equivalent to Turing-computability. This book is a valuable resource for undergraduate or graduate students.

Table of Contents


List of Special Symbols


I. Mathematical Basis

1. Sets and Functions

2. Alphabets and Words

3. Predicates

4. Induction and Inductive Definition

5. Countability and Enumeration Functions

II. Introduction to Computability

1. Implications of the Concept of Effectiveness

2. Turing Machines—Preliminary Definitions

3. Universal Turing Machines and the Halting Problem

4. Purpose, Significance, and Plan

III. Description of Turing Machines by Predicates

1. S-Rudimentary Predicates

2. Turing Machines—Formal Definitions

3. Gödel Words and the Basic Simulation Predicates

4. The Basic Simulation Predicates Are S-Rudimentary

5. Existentially Definable Predicates, μ-Rudimentary Functions

IV. Decision of Predicates by Turing Machines

1. Subroutines and Flow Charts

2. Standard Computability

3. Turing Machine Closure Properties

4. Auxiliary Tape Symbols

V. The Normal Form Theorems and Consequences

1. The Normal Form Theorems and a Universal Turing Machine

2. Positive Consequences

3. Negative Consequences

4. Kleene's Smn Theorem

VI. Other Formulations of Computability

1. Definition of Computability by Recursion

2. Every General Recursive Function Is Recursive

3. Every Recursive Function Is General Recursive

4. The One-Letter Case

5. Semi-Thue Systems

6. Post Canonical Systems




No. of pages:
© Academic Press 1973
Academic Press
eBook ISBN:

About the Author

Neil D. Jones

About the Editor

Robert L. Ashenhurst

Ratings and Reviews