Computable Functions

by Vereshchagin, Nikolai Konstantinovich; Shen, A.

• ISBN13: 9780821827321
• ISBN10: 0821827324
• Format: Paperback
• Copyright: 2003-01-01
• Publisher: Amer Mathematical Society

Summary

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 that would like to learn basics of the general theory of computation. The book is also an ideal reference source for designing a course.

Table of Contents

Preface	vii
Computable Functions, Decidable and Enumerable Sets	1	(10)
Computable functions	1	(2)
Decidable sets	3	(1)
Enumerable sets	4	(3)
Enumerable and decidable sets	7	(1)
Enumerability and computability	8	(3)
Universal Functions and Undecidability	11	(8)
Universal functions	11	(2)
The diagonal construction	13	(1)
Enumerable undecidable set	14	(2)
Enumerable inseparable sets	16	(1)
Simple sets: The Post construction	17	(2)
Numberings and Operations	19	(8)
Godel universal functions	19	(4)
Computable sequences of computable functions	23	(1)
Godel universal sets	24	(3)
Properties of Godel Numberings	27	(14)
Sets of numbers	27	(4)
New numbers of old functions	31	(3)
Isomorphism of Godel numberings	34	(2)
Enumerable properties of functions	36	(5)
Fixed Point Theorem	41	(14)
Fixed point and equivalence relations	41	(3)
A program that prints its text	44	(2)
System trick: Another proof	46	(3)
Several remarks	49	(6)
m-Reducibility and Properties of Enumerable Sets	55	(16)
m-reducibility	55	(2)
m-complete sets	57	(1)
m-completeness and effective nonenumerability	58	(4)
Isomorphism of m-complete sets	62	(2)
Productive sets	64	(3)
Pairs of inseparable sets	67	(4)
Oracle Computations	71	(22)
Oracle machines	71	(3)
Relative computability: Equivalent description	74	(2)
Relativization	76	(3)
O'-computations	79	(3)
Incomparable sets	82	(3)
Friedberg-Muchnik Theorem: The general scheme of construction	85	(2)
Friedberg-Muchnik Theorem: Winning conditions	87	(2)
Friedberg-Muchnik Theorem: The priority method	89	(4)
Arithmetical Hierarchy	93	(14)
Classes Σn and Πn	93	(3)
Universal sets in Σn and Πn	96	(2)
The jump operation	98	(5)
Classification of sets in the hierarchy	103	(4)
Turing Machines	107	(16)
Simple computational models: What do we need them for?	107	(1)
Turing machines: The definition	108	(2)
Turing machines: Discussion	110	(3)
The word problem	113	(1)
Simulation of Turing machines	114	(4)
Thue systems	118	(2)
Semigroups, generators, and relations	120	(3)
Arithmeticity of Computable Functions	123	(16)
Programs with a finite number of variables	123	(3)
Turing machines and programs	126	(2)
Computable functions are arithmetical	128	(4)
Tarski and Godel's Theorems	132	(2)
Direct proof of Tarski and Godel's Theorems	134	(2)
Arithmetical hierarchy and the number of quantifier alternations	136	(3)
Recursive Functions	139	(20)
Primitive recursive functions	139	(1)
Examples of primitive recursive functions	140	(1)
Primitive recursive sets	141	(2)
Other forms of recursion	143	(3)
Turing machines and primitive recursive functions	146	(2)
Partial recursive functions	148	(4)
Oracle computability	152	(2)
Estimates of growth rate. Ackermann's function	154	(5)
Bibliography	159	(2)
Glossary	161	(2)
Index	163