Bridges D.S. — Computability: A mathematical sketchbook :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Bridges D.S. — Computability: A mathematical sketchbook

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Computability: A mathematical sketchbook

Автор: Bridges D.S.

Аннотация:

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.

Язык:

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1994

Количество страниц: 190

Добавлена в каталог: 27.01.2014

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

      93 166-167
      29 125
      57
      122
      98
      48
      77 156
      57 143
      19 27 57 126 143
      138
      28 125
$power\prime$       29 125
$R_{c}$       53
property      45 135
Theorem      43
      27 126
      126
      29 126
      77 156
      21 27 57 143
      88
$\bar{k}$       49
$\mathcal{P}(N)$       138
Acceptable programming system      45 83 161
Ackermann’s function      33 129
Admissible      8
Admissible for minimisation      28
Almost all      95
Almost everywhere      95
Alphabet      3
Baire category      115
Base functions      26 125
BLANK      5
Blum’s axioms      93
Boolean functions      21 122
Canonical enumeration      41
Cantor’s theorem      50
Cartesian product      1
Characteristic function      38
Church — Markov — Turing thesis      32 161
Church’s thesis      32
Classical logic      ix
Code      39
Completes a computation      8
complexity      93
Complexity class      101 170
Complexity function      93
Complexity measure      93
Composite      2
composition      125
Compression theorem      104
Computable -ary expansion      59
Computable analysis      66
Computable partial function      22 40 52 56-57 87 145
Computable real number      53
Computable real number generator      53
Computable sequence      66
Computation      8
Concatenation of sets      3
Concatenation of strings      3
Configuration      7
Configuration, reaches      37
Constructive logic      ix
Continuum Hypothesis      viii
Converges effectively      66
Converges effectively and uniformly      67
Cost function      93
Countable      35
Cyclic left shift      17
Decidability Problem      47
Decidable      48
Decision problem      47
defined      1
Diagonal argument      50
Domain      1
Double Recursion Theorem      83
Effective enumeration      35 40-41
Effective enumeration, diagonal      80
Effective sequence of open intervals      67
Effectively continuous      69
Effectively enumerable      35
Effectively uniformly continuous      69
Empty partial function      21 120
Empty string      3
Encoding      39 87
Enumeration      35
Equivalence problem      47
Erase      21
Factorial function      28 125
Fails to complete a computation      10
Final configuration      8
Finite subfunction      86
Gap theorem      101 103
Gap Theorem, Uniform Version      103
Goldbach conjecture      89

Halmos      169
halt      11
Halt state      6
Halting problem      47
Halts in steps      37
Halts in at most steps      37
Heine — Borel theorem      67
Identity function      76
Inadmissible      8
Increasing      66
Index of $\varphi^{(n)}_{\nu}$       41
Index set      98
Index, of a Turing machine      41
Infinitely often      95
Initial configuration      8
Input      8
Input alphabet      6
Intuitionistic logic      ix
Iterate of a set      3
Kleene star      3
Kreisel — Lacombe — Schoenfield — $\check{C}$ eitin Theorem      70
Lambda calculus      26
Language      3
Lebesgue measure      115
Lend      7
Length of a string      3
Lisp      26 77
Loops      13 16
Minimisation      28
Monotone sequence principle      151
Moves of a Turing machine      6
Natural numbers      1
Noncomputable real number      53
Normalised binary Turing machine      38
Output      8
Parametrisation theorem      43
Park      11
Partial function      1
Partial function, computed      19
Partial recursive function      26 28
Primitive recursion      27 125
Primitive recursive functions      27
PRODUCT      2
Projection      1
Projection function      126
Projection functions      27
Proper subset      78
Pseudo-speed-up Theorem      106
RANGE      1
Rational numbers      1
Reached in steps      8
Reached in one step      7
Real numbers      1
Recursion theorem      80
Recursion Theorem, Extended      83
RECURSIVE      38
Recursive analysis      66
Recursive enumeration      35
Recursively enumerable      35
Reduction      157
rend      7
Respects indices      79
Rice’s theorem      78
Rice’s Theorem, Extended Version      90
Rogers’ isomorphism theorem      45
Self-replicating virus      84
SEQUENCE      1
Specker’s Theorem      67
Speed-up property      106
Speed-up theorem      106 110
Start state      6
State      6
State diagram      12
State transition function      6
State transition table      12
String      3
Successor function      27
SUM      2
Tape alphabet      6
Term of a string      3
Total partial function      1
Turing machine computable      22
Turing machine module      11
Turing machine, binary      19
Turing machine, deterministic      6
Turing machine, formal definition      6
Turing machine, informal description      5
Turing machine, nondeterministic      6
Unary representation      19
Undecidable      48
UNDEFINED      1
Universal property      45 135
Universal Turing machine      42
Weierstrass approximation theorem      70 72
Zermelo — Fraenkel set theory      viii 161
Zero function      26 126

О проекте