Эббинхауз Г.-Д., Якобс К., Ман Ф.-К. — Машины Тьюринга и рекурсивные функции :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Красота

Эббинхауз Г.-Д., Якобс К., Ман Ф.-К. — Машины Тьюринга и рекурсивные функции

Эббинхауз Г.-Д., Якобс К., Ман Ф.-К. — Машины Тьюринга и рекурсивные функции

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

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

Название: Машины Тьюринга и рекурсивные функции

Авторы: Эббинхауз Г.-Д., Якобс К., Ман Ф.-К.

Аннотация:

Этот коллективный труд немецких математиков содержит элементарное изложение теории машин Тьюринга и рекурсивных функций - важного раздела современной математической логики, нашедшего широкое применение в кибернетике. Помимо основ этой теории, книга содержит ряд существенных результатов, включая достижения последнего времени (в частности, результаты Колмогорова о связи машин Тьюринга с основаниями теории вероятностей). Изложение ведется строго, но доступно, содержит много примеров и пояснений. Книгу с интересом прочтут читатели разных категорий, начиная от учащихся старших классов школ с математической специализацией и кончая научными работниками и преподавателями высшей школы.

Язык:

Рубрика: Computer science/Вычислимость/

Серия: Современная математика. Популярная серия

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

ed2k: ed2k stats

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

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

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

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

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

$inf{\o}=\infty$       190
$K(\omega)$       194
$K_A(\omega)$       190
$T^{\S}$ -машина      56
$[\omega]$ (цилиндрическое множество для слова $\omega$ )      202
$\lambda$ -определимая функция      11
$\mathbf{N}$ (множество натуральных чисел)      13 28 123 129 134 136
$\mu$ -рекурсивная функция      11
$\rho_0(A)$       236
$\rho_1(A)$       236
0-1-блоки      см. «Блок» «Блоки»
0-1-последовательиость      183 196 199 204 209
0-1-последовательности      216
0-1-последовательности машинно-порожденные      217
0-1-последовательности равномерно чезаровские      234 238
0-1-последовательности случайные      183 186 196 201 207 209 213
0-1-последовательности специальные      219
0-1-последовательность квазислучайная      196 207
0-1-слово      183 188 193 199 205 206
10-я проблема Гильберта      10 19
A(p|n)      185
Ars Combinatoria      90
Ars Magna      90
M(T) (машина с таблицей T)      16
modus ponens      112 122 142
n-местная функция      52 95
n-членная последовательность      12 34 65
Principia Mathematica      11 84
Автоматически работающая машина      20
Азбука Морзе      74
Аккерман      151 182
Аксиома      112 117 133 142
Аксиома выбора      179
Аксиоматическая система Пеано      137
Алгебра      10 90
Алгебра блоков      217 247
Алгоритм      9 13 20 28 32 68 88 162 185 219
Алгоритм деления      10
Алгоритм Евклида      9
Алгоритмическая неразрешимость      11
Алгоритмическое решение математической задачи      11
Алгоритмы конкретные      11 20
Алгоритмы Маркова      11
Алгоритмы экстенсионально равные      18 23
Алфавит      4 55 68 74 82 87 90 95 108 124 140 163
Алфавит входной      14 36 43 45 56
Алфавит выходной      14 56
Алфавит переменных      110
Алфавит предикатов      110
Алфавит рабочий      14 25 27 31 36 39 45 56 63 69 76 82 98 107 112 116 124
Альхваризми      10
Анализ      90
Аналитическая геометрия      10
Анкета      208
Антиномия Рассела      104
Апериодические почти-периодические последовательности      233
Апериодичность      226
Арабская математика      10 90
Арифметизация формальной системы      135 105 145
Арифметика      74 89 126 133
Арифметика Пеано      137
Арифметические двучленные функции      135
Арифметический язык      156
Арифметическое выражение      126 134
Арифметическое высказывание      126 133 144
Арифметическое высказывание истинное      129 133 145
Арифметическое высказывание ложное      131
Арифметическое отношение      135
Асимметричная монета      189
Асимптотически оптимальный      192 194 213
Асимптотический      191
Атомарная (Ф-) формула      111 117 120 124
Атомарное выражение      154
Атомарное заключение      84
Бабушка      246
Базис окрестностей      203
Базис формальный      110 117
Барков      216
Бергер      159 182
Бернайс      158
Бернулли      186 214 225
Бернулли пространство      225
Бернулли эксперимент      186
Бесконечная лента      224
Бесконечно сложное слово      190
Бесконечное произведение 0-1-блоков      222
Бесконечное произведение действительных чисел      237
Бесконечные произведения      216
Беспорядочная последовательность      187
Биллингслей      6
Блок      217
Блок жесткий      247
Блок начальный      222
Блок полужесткий      247
Блок пустой      220
Блок равномерно-чезаровскнй      234 240
Блок чезаровский      234
Блок-схема      34
Блюменталь      188 214
Бонсдорф-Фабель-Риихима      230 247
Борель      198 214
Брайман      189 214
Брауэр      118 149
Бросание монеты      15 187
Буква      12 25 34 39 49 54 59 69 75 83 84
Буква пустая (несобственная)      13 21
Буква собственная      12 49 58 69 120 123
Буквы вспомогательные      34 55
Бун      126
Бурбаки      90 149
Бюхи      150 159 172 182
в.Т. (вычислимость по Тьюрингу)      31
Вальд      187 215
Вальс бесконечного порядка      183 219
Ван      150 159 181
Вейль, Г.      216 247
Взаимная простота      147
Взаимно однозначная функция      48 53 82 94 96
Виль      187 и след. 215
Внешняя информация      16
Внутренняя музыка 0-1-последовательности      219
Воспринимаемая программа      185 193
Воспроизводимость      15
Все истинные высказывания      10 90
Все теоретико-вероятностные высказывания      189 211
Вспомогательные буквы      34 55
Входной алфавит      14 36 43 45 56
Вхождение блоков      226
Вхождение свободное      127
Вхождение связанное      154
Вывод относительно исчисления      108
Выводимая (Ф-) формула      112 120
Выводимое выражение      151
Выводимое слово      108
Выводимые объекты исчисления      106
Выводимые слова исчисления      108
Выдержать тест      189 207
Выполнимое выражение      151 156 159 172 177
Выполнимость выражений универсальная      159
Выражение      127 150 155 171 176
Выражение арифметическое      126 134
Выражение атомарное      154
Выражение выводимое      151
Выражение выполнимое      151 156 159 172 177
Выражение замкнутое      154 157 176 182
Выражение предваренное      155 157
Выражение узкой логики предикатов      154
Выражение числовое      135
Выражение, универсально выполнимое      159
Выражения равновыполнимые      157 177 182

Выражения эквивалентные      157
Высказывание арифметическое      126 133;
Выходной алфавит      14 56
Вычисление без вспомогательных букв      34 55 69
Вычисление нормированное      32 47 54 63 68 83 98 107 119 125
Вычисление функции      31 47 52 82 124
Вычисления (проведение вычислений)      22 29 68 119
Вычислимая по Тьюрингу функция      9 19
Вычислимая функция      17 31 88 91 185
Вычислимость      9 17 88 91
Вычислимость по Тьюрингу обратной функции      33 34
Вычислитель      22
Вычислительная процедура      17 91
Гарантирующая вероятность теста      208
Генетический материал      245
Геометрия аналитическая      10
Герб и решетка      182
Герхард      90 149
Гетоор      188 214
Гёделевский номер (индекс)      82 103
Гёделевский предикат      145
Гёделизация      14 70 82
Гёдель      11 84 90 105 135 145 149 158
Гёделя теорема о неполноте      11 105
Гёделя теорема о полноте      90
Гильберт      10 19 216 247
Гильберта 10-я проблема      10 19
Гипотеза Римана      17 18
График функции      92
Графические схемы      11
Группы      118 126
Группы кристаллографии      211
Двоичное представление числа      185 191 201
Двучленные функции      99 102
Действительные числа      105 137 198
Декарт      10
Декодирующая машина      65
Деление с остатком      146
Десятичное представление числа      86
Диагональная игра «домино»      159 162 179
Диагональная проблема для игры «домино»      159 162 180
Диагональное покрытие      162 180
Диагональное условие      179
Диаграмма Тьюринга      34 38 48 53 58 63 76 100 106
Диаграмма Тьюринга составленная из элементарных машин      54 60 100
Диаметр      203
Диофантово множество      19 149
Диофантово приближение      198
Диофантовы уравнения      19
Длина (0-1-) блока      219 226 243
Длина слова      12 16
Для всех      127
Доказательство невозможности      11
Домино      160 165 170 180
Домино угловое      168
Домино эквивалентные      161
Дополнительная информация      174
Дополнительное условие      186 190
Дочерняя последовательность      245
Дынкин      188 214
Дэвис      19 84 118 149
Евклида алгоритм      9
Единица умножения блоков      221
Жесткий блок      247
Жордан      216
Задание программы      185 195
Задачи      245
Заключение      112
Заключение атомарное      84
Закон ассоциативности для умножения блоков      221
Закон больших чисел      211
Закон коммутативности      220
Замена переменной словом      111
Замкнутое выражение      154 157 176 182
Замкнутое множество      203
Запись      21 28 33 58 74 77 79 99 119
Запись на ленте      22 27 32 58 74 77 99
Запись текущая      21 28
Значение      129
Значение вычислимой по Тьюрингу функции      31
Зонке      216
Игра «домино»      150 159 161 166 171
Игра «домино» диагональная      159 173 179
Игра «домино» угловая      161 166 171 181
Изменение содержимого ячейки      21 27 36
Изоморфизм полугрупп      12
ИЛИ      132 133
Имена домино      161
Импликация филоновская      133
Индекс (гёделевский номер)      82
Индермарк      118 149
Индивидный символ      153 172 177
Индивидный символ свободный      154 157 178
Индивидный символ связанный      154 178
Индукция полная      109 111 221 230
Интерпретация      156
Информационная ячейка      22
Информация внешняя      16
Информация дополнительная      174
Исключение истории проведения вычислений      22
Исключение функциональных символов      157 177
Истинное арифметическое высказывание      126 129 133 145
Исторические замечания      9 10 90 91
История проведения вычислений      22
Исчисление      15 88 107 108
Исчисление логическое      151
Исчисление подстановок      111
Исчисление предикатов первой ступени      153
Какутани      216 223 247
Какутани последовательности      223 229 242
Кальмар      11 84 158
Канонические системы Поста      117
Кантор      105
Кар      150 159 181
Квадрант      162
Квадрат угловой      162
Квадраты чисел      110
Квазисистемы Туэ      117
Квазислучайная (0-1-) последовательность      196 207
Квантор      31 154
Кини      216 219 245 247
Кини последовательность (тернарная)      219 222 229
Кирхер      90
Китайская теорема об остатках      135 145
Классический квантор существования      31
Классы алгоритмов      11 18 68
Классы выражений      150 155 160 172 177
Классы исчислений      108
Клини      9 11 74 82 85 88 149
Клини теорема о перечислении      9 74 82 88 102 189 192 210
Когерентное покрытие      163
Код      134
Кодировать      54
Кодирующая машина      65
Кокстер      216 247
Коллектив      187
Колмогоров      6 184 186 188 190 196 214
Колмогоровская мера сложности      184
Коммутативность      220
Компактное метрическое пространство      202
Компактное множество      204
Компоненты блока      219
Кон-Фоссен      216 247
Конечная конфигурация      28 78
Конечная позиция      29
Конечность описания алгоритма      14
Конечные множества (Ф-) формул      111
Конкретные алгоритмы      11 20
Конструктивные объекты      13 19
Континуум      223

1 2 3

Реклама

© Электронная библиотека попечительского совета мехмата МГУ, 2004-2024

Электронная библиотека мехмата МГУ

Valid HTML 4.01!

|

Valid CSS!

О проекте