Volume: 19; 2003; 166 pp; Softcover
MSC: Primary 03;
Print ISBN: 978-0-8218-2732-1
Product Code: STML/19
List Price: $39.00
Individual Price: $31.20
Electronic ISBN: 978-1-4704-2133-5
Product Code: STML/19.E
List Price: $36.00
Individual Price: $28.80
You may also like
Computable Functions
Share this pageA. Shen; N. K. Vereshchagin
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.
Readership
Undergraduates, graduate students, research mathematicians, and computer scientists and programmers interested in the general theory of computation.
Reviews & Endorsements
Material is a presented quite clearly and with a minimum of fuss … an excellent text for a first course in computability.
-- Mathematical Reviews
Table of Contents
Table of Contents
Computable Functions
- Cover Cover11 free
- Title i2 free
- Copyright ii3 free
- Contents iii4 free
- Preface vii8 free
- Chapter 1. Computable Functions, Decidable and Enumerable Sets 110 free
- Chapter 2. Universal Functions and Undecidability 1120
- Chapter 3. Numberings and Operations 1928
- Chapter 4. Properties of Godel Numberings 2736
- Chapter 5. Fixed Point Theorem 4150
- Chapter 6. m-Reducibility and Properties of Enumerable Sets 5564
- Chapter 7. Oracle Computations 7180
- § 1. Oracle machines 7180
- §2. Relative computability: Equivalent description 7483
- §3. Relativization 7685
- §4. O'-computations 7988
- §5. Incomparable sets 8291
- §6. Friedberg-Muchnik Theorem: The general scheme of construction 8594
- §7. Friedberg-Muchnik Theorem: Winning conditions 8796
- §8. Friedberg-Muchnik Theorem: The priority method 8998
- Chapter 8. Arithmetical Hierarchy 93102
- Chapter 9. Turing Machines 107116
- Chapter 10. Arithmeticity of Computable Functions 123132
- § 1. Programs with a finite number of variables 123132
- §2. Turing machines and programs 126135
- §3. Computable functions are arithmetical 128137
- §4. Tarski and Gödel's Theorems 132141
- §5. Direct proof of Tarski and Gödel's Theorems 134143
- §6. Arithmetical hierarchy and the number of quantifier alternations 136145
- Chapter 11. Recursive Functions 139148
- § 1. Primitive recursive functions 139148
- §2. Examples of primitive recursive functions 140149
- §3. Primitive recursive sets 141150
- §4. Other forms of recursion 143152
- §5. Turing machines and primitive recursive functions 146155
- §6. Partial recursive functions 148157
- §7. Oracle computability 152161
- §8. Estimates of growth rate. Ackermann's function 154163
- Bibliography 159168
- Glossary 161170
- Index 163172
- Back Cover Back Cover1178