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