Algorithms and recursive functions

Title......Page 2
Foreword......Page 4
Notation......Page 6
Introduction......Page 15
1.1. Alphabet. Words......Page 23
1.2. Functions. Terms......Page 25
1.3. Algebras......Page 30
1.4. Coding......Page 33
Examples & exercises......Page 35
2.1. Composition of partial functions......Page 36
2.2. Primitive recursion operator......Page 38
2.3. Operation of minimalization......Page 44
2.4. General recursive functions......Page 50
Addenda, examples & exercises......Page 52
3.1. Operations of summation & majorized inversion......Page 54
3.2. Primitive recursiveness of certain arithmetic functions......Page 58
3.3. Enumeration of pairs & n-tuples of numbers......Page 65
3.4. Interdependence of primitive recursive operators & minimalization operators......Page 70
3.5. One-place primitive recursive functions......Page 74
Addenda, examples & exercises......Page 82
4.1. Recursive & primitive recursive sets......Page 84
4.2. Recursively enumerable sets......Page 86
4.3. Generated sets......Page 89
4.4. Sets of n-tuples of natural numbers......Page 92
Examples & exercises......Page 98
5.1. Recursions of the second order......Page 99
5.2. Universal general recursive function......Page 104
5.3. Rapidly growing functions......Page 111
5.4. Inversion of functions. Robinson's algebra......Page 114
Addenda, examples & exercises......Page 119
6.1. Parametrization of partial recursive functions......Page 120
6.2. Universal partial recursive functions......Page 126
6.3. Completion of a function, Construction of a non-recursive recursively enumerable set......Page 129
6.4. Investigation of Kleene's representation......Page 133
Addenda, examples & exercises......Page 136
7.1. Kleene's universal functions......Page 139
7.2. Kleene's enumeration......Page 142
7.3. Post's enumeration......Page 145
7.4. Single-valued enumerations......Page 151
Addenda, examples & exercises......Page 160
8. Reducibility & creativity of sets......Page 161
8.1. Reducibility & m-equivalence of sets......Page 162
8.2. Productive & creative sets......Page 164
8.3. Simple sets......Page 168
8.4. Maximal sets......Page 169
Addenda, examples & exercises......Page 174
9.1. Isomorphism & equivalence of enumerations......Page 179
9.2. One-one-reducibility of enumerations......Page 183
9.3. Total enumerations......Page 191
9.4. Families of objects of enumerated collections......Page 196
Addenda, examples & exercises......Page 199
10.1. m-universal systems of sets......Page 200
10.2. Creative systems of sets......Page 204
10.3. Recursively inseparable sets......Page 208
Addenda, examples & exercises......Page 211
11. Word sets & functions......Page 213
11.1. Word sets......Page 214
11.2. Fundamental word operators......Page 218
11.3. Direct definition of the class of partial recursive word functions......Page 224
Addenda, examples & exercises......Page 227
12.1. Turing-Post machines......Page 228
12.2. Computable functions......Page 235
12.3. Synthesis of Turing machines......Page 240
12.4. Theorems on the graph & on the existence of universal partial recursive functions......Page 253
12.5. Universal machines......Page 260
Addenda, examples & exercises......Page 263
13.1. The word problem for semigroups......Page 265
13.2. Identically true formulas of the first order predicate calculus......Page 273
13.3. Arithmetical sets......Page 280
13.4. Second order formulas......Page 285
Addenda, examples & exercises......Page 287
14. Normal algorithms & operator algorithms......Page 293
14.1. Formal systems, Post productions......Page 294
14.2. Normal algorithms......Page 298
14.3. Operator algorithms......Page 301
Addenda & examples......Page 310
15.1. General multitape machines......Page 311
15.2. Minsky machines......Page 314
15.3. Homogeneous productions. TAG systems......Page 324
Addenda, examples & exercises......Page 329
16. Diophantine equations......Page 332
16.1. Diophantine predicates & functions......Page 333
16.2. Arithmetic representation......Page 339
16.3. Representability of natural numbers by polynomials......Page 344
16.4. Exponential equations......Page 347
Addenda & examples......Page 355
Literature......Page 357
Index......Page 365