Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Computable Functions
 
A. Shen Independent University of Moscow, Moscow, Russia
N. K. Vereshchagin Moscow State Lomonosov University, Moscow, Russia
Computable Functions
Softcover ISBN:  978-0-8218-2732-1
Product Code:  STML/19
List Price: $59.00
Individual Price: $47.20
eBook ISBN:  978-1-4704-2133-5
Product Code:  STML/19.E
List Price: $49.00
Individual Price: $39.20
Softcover ISBN:  978-0-8218-2732-1
eBook: ISBN:  978-1-4704-2133-5
Product Code:  STML/19.B
List Price: $108.00 $83.50
Computable Functions
Click above image for expanded view
Computable Functions
A. Shen Independent University of Moscow, Moscow, Russia
N. K. Vereshchagin Moscow State Lomonosov University, Moscow, Russia
Softcover ISBN:  978-0-8218-2732-1
Product Code:  STML/19
List Price: $59.00
Individual Price: $47.20
eBook ISBN:  978-1-4704-2133-5
Product Code:  STML/19.E
List Price: $49.00
Individual Price: $39.20
Softcover ISBN:  978-0-8218-2732-1
eBook ISBN:  978-1-4704-2133-5
Product Code:  STML/19.B
List Price: $108.00 $83.50
  • Book Details
     
     
    Student Mathematical Library
    Volume: 192003; 166 pp
    MSC: 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.

    Readership

    Undergraduates, 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
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Permission – for use of book, eBook, or Journal content
    Accessibility – to request an alternate format of an AMS title
Volume: 192003; 166 pp
MSC: 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.

Readership

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
Review Copy – for publishers of book reviews
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
You may be interested in...
Please select which format for which you are requesting permissions.