# Computable Functions (Google eBook)

American Mathematical Soc., 2003 - Mathematics - 166 pages
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.

### What people are saying -Write a review

We haven't found any reviews in the usual places.

### Contents

 Computable Functions Decidable and Enumerable Sets 1 Universal Functions and Undecidability 11 Numberings and Operations 19 Properties of Gödel Numberings 27 Fixed Point Theorem 41 mReducibility and Properties of Enumerable Sets 55
 Oracle Computations 71 Arithmetical Hierarchy 93 Turing Machines 107 Arithmeticity of Computable Functions 123 Recursive Functions 139 Copyright

### Popular passages

Page 159 - George S. Boolos, John P. Burgess, and Richard C. Jeffrey. Computability and Logic.
Page 2 - ... —1, 0, and 1 for x < 0, x = 0, and x > 0, respectively, is not.
Page 159 - Cambridge, 1980. [4] Yu. L. Ershov, Theory of numberings. Nauka, Moscow, 1977. (Russian) [5] SK Kleene, Introduction to metamathematics.