# Computability Theory

## 1st Edition

### An Introduction

Authors:
Editors:
eBook ISBN: 9781483218489
Published Date: 28th January 1973
Page Count: 168
Sales tax will be calculated at check-out Price includes VAT/GST
24.95
19.99
31.95
Unavailable
Price includes VAT/GST

## Description

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.

﻿Preface

List of Special Symbols

Introduction

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

References

Index

No. of pages:
168
Language:
English
Published:
Imprint: