Computable Functions

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


Computable Functions Decidable and Enumerable Sets
Universal Functions and Undecidability
Numberings and Operations
Properties of Gödel Numberings
Fixed Point Theorem
mReducibility and Properties of Enumerable Sets
Oracle Computations
Arithmetical Hierarchy
Turing Machines
Arithmeticity of Computable Functions
Recursive Functions

Common terms and phrases

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.

Bibliographic information