Computability: A Mathematical SketchbookSpringer Science & Business Media, 14. jan. 1994 - 178 strani Aimed at mathematicians and computer scientists who will only be exposed to one course in this area, Computability: A Mathematical Sketchbook provides a brief but rigorous introduction to the abstract theory of computation, sometimes also referred to as recursion theory. It develops major themes in computability theory, such as Rice's theorem and the recursion theorem, and provides a systematic account of Blum's complexity theory as well as an introduction to the theory of computable real numbers and functions. The book is intended as a university text, but it may also be used for self-study; appropriate exercises and solutions are included. |
Vsebina
What Is a Turing Machine? | 5 |
Computable Partial Functions | 19 |
Effective Enumerations | 35 |
Computable Numbers and Functions | 47 |
Rices Theorem and the Recursion Theorem | 75 |
Abstract Complexity Theory | 93 |
Solutions to Exercises | 117 |
Solutions for Chapter 1 | 118 |
Solutions for Chapter 2 | 120 |
Solutions for Chapter 3 | 130 |
Solutions for Chapter 4 | 136 |
Solutions for Chapter 5 | 156 |
References | 173 |
| 176 | |
Druge izdaje - Prikaži vse
Pogosti izrazi in povedi
acceptable programming system Algebraic algorithm applied binary Turing machine blank Cantor's Theorem Church-Markov-Turing thesis completes a computation complexity measure computability theory computable partial function computable real number computable sequence configuration construct a total contradicts Define a computable Define a total Design a Turing diagram domain domain(n effective enumeration everywhere Exercise exists a computable exists a total finite func function f given halting problem Hence IND(ƒ input alphabet leftmost cell Lemma Let f machine that computes mapping moves left natural number nonempty normalised binary Turing number generator converging output positive integer primitive recursive Proposition Prove rational numbers read/write head Recursion Theorem recursive set respects indices Rice's Theorem s-m-n theorem sequence of total Speed-up Theorem string Suppose symbol tape alphabet total computable function total function Turing machine computable Turing machine module undefined otherwise undefined undefined vi(n writes Yi(n
Priljubljeni odlomki
Stran 2 - A) + b in the sense that the left hand side is defined if and only if the right hand side is defined, and then they are equal.
Navedki za to knjigo
Foundations of Real and Abstract Analysis, 146. izdaja Douglas S. Bridges Predogled ni na voljo - 1998 |