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.

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

Common terms and phrases

Popular passages

Page 159 - George S. Boolos, John P. Burgess, and Richard C. Jeffrey. Computability and Logic.
Page 159 - Cambridge, 1980. [4] Yu. L. Ershov, Theory of numberings. Nauka, Moscow, 1977. (Russian) [5] SK Kleene, Introduction to metamathematics.

Bibliographic information