Computable Functions (Student Mathematical Library, Vol. 19) (Student Mathematical Library, V. 19)

In 1936, before the development of modern computers, Alan Turing proposed the concept of a machine that would embody the interaction of mind, machine, and logical instruction. The idea of a 'universal machine' inspired the notion of programs stored in a computer's memory. Nowadays, the study of computable functions is a core topic taught to mathematics and computer science undergraduates. Based on the lectures for undergraduates at Moscow State University, this book presents a lively and concise introduction to the central facts and basic notions of the general theory of computation.It begins with the definition of a computable function and an algorithm and discusses decidability, enumerability, universal functions, numberings and their properties, $m$-completeness, the fixed point theorem, arithmetical hierarchy, oracle computations, and degrees of unsolvability. The authors complement the main text with over 150 problems. They also cover specific computational models, such as Turing machines and recursive functions. The intended audience includes undergraduate students majoring in mathematics or computer science, and all mathematicians and computer scientists who would like to learn basics of the general theory of computation. The book is also an ideal reference source for designing a course. Cover 1 Title 2 Copyright 3 Contents 4 Preface 8 Chapter 1. Computable Functions, Decidable and Enumerable Sets 10 § 1. Computable functions 10 §2. Decidable sets 12 §3. Enumerable sets 13 §4. Enumerable and decidable sets 16 §5. Enumerability and computability 17 Chapter 2. Universal Functions and Undecidability 20 § 1. Universal functions 20 §2. The diagonal construction 22 § 3. Enumerable undecidable set 23 §4. Enumerable inseparable sets 25 §5. Simple sets: The Post construction 26 Chapter 3. Numberings and Operations 28 § 1. Godel universal functions 28 §2. Computable sequences of computable functions 32 § 3. Godel universal sets 33 Chapter 4. Properties of Godel Numberings 36 § 1. Sets of numbers 36 §2. New numbers of old functions 40 §3. Isomorphism of Godel numberings 43 §4. Enumerable properties of functions 45 Chapter 5. Fixed Point Theorem 50 § 1. Fixed point and equivalence relations 50 §2. A program that prints its text 53 §3. System trick: Another proof 55 §4. Several remarks 58 Chapter 6. m-Reducibility and Properties of Enumerable Sets 64 § 1. m-reducibility 64 §2. m-complete sets 66 §3. m-completeness and effective nonenumerability 67 §4. Isomorphism of m-complete sets 71 §5. Productive sets 73 §6. Pairs of inseparable sets 76 Chapter 7. Oracle Computations 80 § 1. Oracle machines 80 §2. Relative computability: Equivalent description 83 §3. Relativization 85 §4. O'-computations 88 §5. Incomparable sets 91 §6. Friedberg-Muchnik Theorem: The general scheme of construction 94 §7. Friedberg-Muchnik Theorem: Winning conditions 96 §8. Friedberg-Muchnik Theorem: The priority method 98 Chapter 8. Arithmetical Hierarchy 102 § 1. Classes Σ[sub(n)] and II[sub(n)] 102 §2. Universal sets in Σ[sub(n)] and II[sub(n)] 105 §3. The jump operation 107 §4. Classification of sets in the hierarchy 112 Chapter 9. Turing Machines 116 § 1. Simple computational models: What do we need them for? 116 §2. Turing machines: The definition 117 §3. Turing machines: Discussion 119 §4. The word problem 122 §5. Simulation of Turing machines 123 §6. Thue systems 127 §7. Semigroups, generators, and relations 129 Chapter 10. Arithmeticity of Computable Functions 132 § 1. Programs with a finite number of variables 132 §2. Turing machines and programs 135 §3. Computable functions are arithmetical 137 §4. Tarski and Gödel's Theorems 141 §5. Direct proof of Tarski and Gödel's Theorems 143 §6. Arithmetical hierarchy and the number of quantifier alternations 145 Chapter 11. Recursive Functions 148 § 1. Primitive recursive functions 148 §2. Examples of primitive recursive functions 149 §3. Primitive recursive sets 150 §4. Other forms of recursion 152 §5. Turing machines and primitive recursive functions 155 §6. Partial recursive functions 157 §7. Oracle computability 161 §8. Estimates of growth rate. Ackermann's function 163 Bibliography 168 Glossary 170 Index 172 A 172 B 172 C 172 D 173 E 173 F 173 G 173 H 173 I 173 J 173 K 173 L 173 M 174 N 174 O 174 P 174 Q 174 R 174 S 174 T 175 U 175 W 175 Back Cover 178 "This lively and concise book is based on the lectures for undergraduates given by the authors at the Moscow State University Mathematics Department and covers the basic notions of the general theory of computation. It begins with the definition of a computable function and an algorithm, and discusses decidability, enumerability, universal functions, numberings and their properties, m-completeness, the fixed point theorem, arithmetical hierarchy, oracle computations, and degrees of unsolvability. The authors also cover specific computational models, such as Turing machines and recursive functions." "The intended audience includes undergraduate students majoring in mathematics or computer science, and all mathematicians and programmers that would like to learn the basics of the general theory of computation."--Jacket This lively and concise book is based on the lectures for undergraduates given by the authors at the Moscow State University Mathematics Department and covers the basic notions of the general theory of computation. It begins with the definition of a computable function and an algorithm and discusses decidability, enumerability, universal functions, numberings and their properties, $m$-completeness, the fixed point theorem, arithmetical hierarchy, oracle computations, and degrees of unsolvability. The authors also cover specific computational models, such as Turing machines and recursive functions. The intended audience includes undergraduate students majoring in mathematics or computer science, and all mathematicians and programmers who would like to learn the basics of the general theory of computation. Shen and Vereshchagin base this text on lectures presented at the Moscow State U. Mathematics Dept., for which they select central notions and facts from the general theory of algorithms. Coverage includes computable functions, decidable and enumerable sets; universal functions and undecidability; numberings and operations; properties of Gdel numberings; fixed point theorem; m -reducibility and properties of enumerable sets; oracle computations; arithmetical hierarchy; Turing machines; arithmeticity of computable functions; and recursive functions. For undergraduate mathematics or computer science majors, mathematicians and programmers. Translated from Russian by V. N. Dubrovskii. Annotation c. Book News, Inc., Portland, OR (booknews.com) Chapter 1. Computable Functions, Decidable And Enumerable Sets Chapter 2. Universal Functions And Undecidability Chapter 3. Numberings And Operations Chapter 4. Properties Of Gödel Numberings Chapter 5. Fixed Point Theorem Chapter 6. $m$-reducibility And Properties Of Enumerable Sets Chapter 7. Oracle Computations Chapter 8. Arithmetical Hierarchy Chapter 9. Turing Machines Chapter 10. Arithmeticity Of Computable Functions Chapter 11. Recursive Functions A. Shen, N.k. Vereshchagin ; Translated By V.n. Dubrovskii. Includes Bibliographical References (p. 159-160) And Index. Based on the lectures for undergraduates at Moscow State University, this book presents a lively and concise introduction to the central facts and basic notions of the general theory of computation. It begins with the definition of a computable function and an algorithm, and discusses decidability, enumerability, universal functions, numberings and their properties, the fixed point theorem, arithmetical hierarchy, oracle computations, and degrees Based on the lectures for undergraduates at Moscow State University, this book offers an introduction to the central facts and basic notions of the general theory of computation. It begins with the definition of a computable function and an algorithm and discusses decidability, enumerability, universal functions, and degrees of unsolvability.