Computability Theory
An Introduction
- 1st Edition - September 20, 2014
- Latest edition
- Author: Neil D. Jones
- Editor: Robert L. Ashenhurst
- Language: English
Computability Theory: An Introduction provides information pertinent to the major concepts, constructions, and theorems of the elementary theory of computability of recursive… Read more
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.
PrefaceList of Special SymbolsIntroductionI. Mathematical Basis 1. Sets and Functions 2. Alphabets and Words 3. Predicates 4. Induction and Inductive Definition 5. Countability and Enumeration FunctionsII. 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 PlanIII. 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 FunctionsIV. Decision of Predicates by Turing Machines 1. Subroutines and Flow Charts 2. Standard Computability 3. Turing Machine Closure Properties 4. Auxiliary Tape SymbolsV. 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 TheoremVI. 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 SystemsReferencesIndex
- Edition: 1
- Latest edition
- Published: September 20, 2014
- Language: English
Read Computability Theory on ScienceDirect