Softcover ISBN:  9780821827321 
Product Code:  STML/19 
List Price:  $39.00 
Individual Price:  $31.20 
Electronic ISBN:  9781470421335 
Product Code:  STML/19.E 
List Price:  $36.00 
Individual Price:  $28.80 

Book DetailsStudent Mathematical LibraryVolume: 19; 2003; 166 ppMSC: Primary 03;
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.ReadershipUndergraduates, graduate students, research mathematicians, and computer scientists and programmers interested in the general theory of computation.

Table of Contents

Chapters

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


Reviews

Material is a presented quite clearly and with a minimum of fuss … an excellent text for a first course in computability.
Mathematical Reviews


RequestsReview Copy – for reviewers who would like to review an AMS bookPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Reviews
 Requests
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.
Undergraduates, graduate students, research mathematicians, and computer scientists and programmers interested in the general theory of computation.

Chapters

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

Material is a presented quite clearly and with a minimum of fuss … an excellent text for a first course in computability.
Mathematical Reviews