## Computable FunctionsIn 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

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 |

### Common terms and phrases

a-computable alphabet answer arbitrary arithmetical hierarchy arithmetical set belongs bijection binary called character class of unary coincides complement completes the proof computable numbering computable permutation computable universal function consider construction corresponding decidable set defined definition denoted domain effectively nonenumerable element empty function encoded enumerable set enumerable subset enumerable undecidable set equivalent exists a computable exists a total finite set finitely many variables Fixed Point Theorem formula func function h given Godel numbering Godel universal function Godel universal set graph Halting Problem halts infinite input integer Lemma m-complete sets m-reducibility natural numbers nonempty obtained oracle output pairs of natural pattern prenex normal form primitive recursive function Problem programming language prove quantifiers recursive set semigroup set of natural set of numbers set of pairs Show specified statement step string Suppose tape tion total computable function total function triples Turing machine unary computable functions unary functions undefined zero

### 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.