Computable FunctionsAmerican Mathematical Soc., 2003 - Всего страниц: 166 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. |
Содержание
1 | |
Chapter 2 Universal Functions and Undecidability | 11 |
Chapter 3 Numberings and Operations | 19 |
Chapter 4 Properties of Godel Numberings | 27 |
Chapter 5 Fixed Point Theorem | 41 |
Chapter 6 mReducibility and Properties of Enumerable Sets | 55 |
Chapter 7 Oracle Computations | 71 |
Chapter 8 Arithmetical Hierarchy | 93 |
Chapter 9 Turing Machines | 107 |
Chapter 10 Arithmeticity of Computable Functions | 123 |
Chapter 11 Recursive Functions | 139 |
159 | |
Glossary | 161 |
163 | |
Back Cover | 169 |
Другие издания - Просмотреть все
Computable Functions Nikolai Konstantinovich Vereshchagin,Alexander Shen Недоступно для просмотра - 2003 |
Часто встречающиеся слова и выражения
a-computable alphabet answer arbitrary arithmetical hierarchy arithmetical set belongs bijection binary called character class of unary class XX complement completes the proof computable numbering computable permutation computable real consider construction decidable set defined definition denoted domain effectively inseparable effectively nonenumerable element empty function encoded enumerable set enumerable undecidable set equivalent exists a computable exists a total finite set finitely many variables Fixed Point Theorem formula func function f Gödel numbering Gödel universal function Gödel universal set Halting Problem halts infinite input integer isomorphism Lemma m-reducible natural numbers obtained oracle pairs of natural partial recursive pattern prenex normal form primitive recursive function Problem programming language prove quantifiers real number 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 U-numbers unary computable functions unary functions undefined Us(n zero