Computability, an introduction to recursive function theory / Nigel Cutland.

Format:

Book

Author/Creator:

Cutland, Nigel.

Language:

English

Subjects (All):

Computable functions.

Recursion theory.

Physical Description:

x, 251 pages : illustrations ; 24 cm

Place of Publication:

Cambridge [Eng.] ; New York : Cambridge University Press, 1980.

Summary:

What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way.

This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians).

Contents:

Prologue. Prerequisites and notation 1

1 Sets 1

2 Functions 2

3 Relations and predicates 4

4 Logical notation 4

1 Computable functions 7

1 Algorithms, or effective procedures 7

2 The unlimited register machine 9

3 URM-computable functions 16

4 Decidable predicates and problems 22

5 Computability on other domains 23

2 Generating computable functions 25

1 The basic functions 25

2 Joining programs together 25

3 Substitution 29

4 Recursion 32

5 Minimalisation 42

3 Other approaches to computability: Church's thesis 48

1 Other approaches to computability 48

2 Partial recursive functions (Godel-Kleene) 49

3 A digression: the primitive recursive functions 51

4 Turing-computability 52

5 Symbol manipulation systems of Post and Markov 57

6 Computability on domains other than N 65

7 Church's thesis 67

4 Numbering computable functions 72

1 Numbering programs 72

2 Numbering computable functions 76

3 Discussion: the diagonal method 79

4 The s-m-n theorem 81

5 Universal programs 85

1 Universal functions and universal programs 85

2 Two applications of the universal program 90

3 Effective operations on computable functions 93

Appendix Computability of the function [sigma subscript n] 95

6 Decidability, undecidability and partial decidability 100

1 Undecidable problems in computability 101

2 The word problem for groups 106

3 Diophantine equations 107

4 Sturm's algorithm 108

5 Mathematical logic 109

6 Partially decidable predicates 112

7 Recursive and recursively enumerable sets 121

1 Recursive sets 121

2 Recursively enumerable sets 123

3 Productive and creative sets 133

4 Simple sets 140

8 Arithmetic and Godel's incompleteness theorem 143

1 Formal arithmetic 143

2 Incompleteness 146

3 Godel's incompleteness theorem 149

4 Undecidability 155

9 Reducibility and degrees 157

1 Many-one reducibility 158

2 Degrees 161

3 m-complete r.e. sets 165

4 Relative computability 167

5 Turing reducibility and Turing degrees 174

10 Effective operations on partial functions 182

1 Recursive operators 182

2 Effective operations on computable functions 189

3 The first Recursion theorem 192

4 An application to the semantics of programming languages 196

11 The second Recursion theorem 200

1 The second Recursion theorem 200

3 Myhill's theorem 210

12 Complexity of computation 212

1 Complexity and complexity measures 213

2 The Speed-up theorem 218

3 Complexity classes 223

4 The elementary functions 225

13 Further study 236.

Notes:

Includes index.

Bibliography: pages [239]-240.

ISBN:

0521223849

OCLC:

5170205