Computable functions / A. Shen, N. K. Vereshchagin ; translated by V.N. Dubrovskii.

Format:

Book

Author/Creator:

Vereshchagin, Nikolai Konstantinovich, 1958-

Contributor:

Shen, A. (Alexander), 1958-

Series:

Student mathematical library 1520-9121 ; v. 19.

Student mathematical library, 1520-9121 ; v. 19

Language:

English

Russian

Subjects (All):

Computable functions.

Physical Description:

viii, 166 pages : illustrations ; 22 cm.

Place of Publication:

Providence, R.I. : American Mathematical Society, [2003]

Contents:

Chapter 1. Computable Functions, Decidable and Enumerable Sets 1

1. Computable functions 1

2. Decidable sets 3

3. Enumerable sets 4

4. Enumerable and decidable sets 7

5. Enumerability and computability 8

Chapter 2. Universal Functions and Undecidability 11

1. Universal functions 11

2. The diagonal construction 13

3. Enumerable undecidable set 14

4. Enumerable inseparable sets 16

5. Simple sets: The Post construction 17

Chapter 3. Numberings and Operations 19

1. Godel universal functions 19

2. Computable sequences of computable functions 23

3. Godel universal sets 24

Chapter 4. Properties of Godel Numberings 27

1. Sets of numbers 27

2. New numbers of old functions 31

3. Isomorphism of Godel numberings 34

4. Enumerable properties of functions 36

Chapter 5. Fixed Point Theorem 41

1. Fixed point and equivalence relations 41

2. A program that prints its text 44

3. System trick: Another proof 46

Chapter 6. m-Reducibility and Properties of Enumerable Sets 55

1. m-reducibility 55

2. m-complete sets 57

3. m-completeness and effective nonenumerability 58

4. Isomorphism of m-complete sets 62

5. Productive sets 64

6. Pairs of inseparable sets 67

Chapter 7. Oracle Computations 71

1. Oracle machines 71

2. Relative computability: Equivalent description 74

3. Relativization 76

4. 0'-computations 79

5. Incomparable sets 82

6. Friedberg-Muchnik Theorem: The general scheme of construction 85

7. Friedberg-Muchnik Theorem: Winning conditions 87

8. Friedberg-Muchnik Theorem: The priority method 89

Chapter 8. Arithmetical Hierarchy 93

1. Classes [Sigma subscript n] and [Pi subscript n] 93

2. Universal sets in [Sigma subscript n] and [Pi subscript n] 96

3. The jump operation 98

4. Classification of sets in the hierarchy 103

Chapter 9. Turning Machines 107

1. Simple computational models: What do we need them for? 107

2. Turing machines: The definition 108

3. Turing machines: Discussion 110

4. The word problem 113

5. Simulation of Turing machines 114

6. Thue systems 118

7. Semigroups, generators, and relations 120

Chapter 10. Arithmeticity of Computable Functions 123

1. Programs with a finite number of variables 123

2. Turing machines and programs 126

3. Computable functions are arithmetical 128

4. Tarski and Godel's Theorems 132

5. Direct proof of Tarski and Godel's Theorems 134

6. Arithmetical hierarchy and the number of quantifier alternations 136

Chapter 11. Recursive Functions 139

1. Primitive recursive functions 139

2. Examples of primitive recursive functions 140

3. Primitive recursive sets 141

4. Other forms of recursion 143

5. Turing machines and primitive recursive functions 146

6. Partial recursive functions 148

7. Oracle computability 152

8. Estimates of growth rate. Ackermann's function 154.

Notes:

Includes bibliographical references (pages 159-160) and index.

ISBN:

0821827324

OCLC:

50841184