Computable Functions

The book is based on lectures for undergraduate students at the Moscow State University Mathematics Department and the content covers a majority of basic notions of general theory of computation, excluding computational complexity. It begins with a definition of computable functions, based on an informal definition of algorithms. Then, the classic notions of topics such as decidability, universal functions, fixed point theorem, enumerable sets, oracle computations and arithmetical hierarchy, are presented, clarified and developed. A precise definition of an algorithm is given in the ninth chapter (Turing machines); the word problem is treated here as well. Chapter 10 (Arithmeticity of computable function), develops the subject on the mentioned precise base; Tarski’s theorem and Gődels’ undecidability theorem are presented. The last chapter is devoted to recursive functions. The book can appropriately provide knowledge of the theme to programmers and to students of mathematics and computer science.

Reviewer: 
jmlč
Book details
Author:  Publisher: 
Published: 
2002
ISBN: 
0-8218-2732-4
Price: 
US$29
Categorisation