ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

Множество рекурсивно перечпслимое 79

- рекурсивное 77

- ретрассируемое 169

- сжатое Гб4

- слабо продуктивное 168

- словарное 205

- частично рекурсивное (относительно...) 43

- эффективно иммунное 171

- - простое 171

- ?1г-универсальное 157

- п-ок натуральных .чисел 86

- - примитивно рекурсивное 86

- - рекурсиьно перечислимое 86 -- рекурсивное 86

Модель 267

Номер функции 99, 136 Нормальная форма Клини 120 Нумерации, односводимость 176 -, одноэквивалентность 176

- рекурсивно изоморфные 174

- эквивалентные 173 Нумерация 133

- алфавитная 205

- вычислимая 146

- геделевокая 133

- Клини 136

- однозначная 146, 172

- полная 183

- Поста 139

- простая 172

- стандартная 147

Оператор минимизации 39, 41

- обращения 41

- примитивной рекурсии 33

- словарный 209 Операция 20, 82

-, изображенная термом 21

- итерирования одноместной частичной функции 69

- композиции одноместных частичных функций 68, 69

- мажорированного обращения 49, 52

- М1шимпзации 41

- - специального вида 66

- общерекурсивная 89

- подстановки 31

- примитивной рекурсии 33

- - - специального впда 64

- сложения одноместных частичных Функцпп 68

- суммирования 49, 50

- суперпозиции 31

- термальная 23

- частично рекурсивная S9 Определяющие соотношения 257 Особый объект 183 Отношение бинарное 218

Память внешняя 219

- внутренняя 220 Подалгебра замкнутая 26

- частичная 26 Полугруппа 254, 255

- свободная 255 Порождающие 27, 257 Последовательность Фибоначчи 59

Предикат 263

- арифметический 271

- диофантовый 325

- показательно диофантовый 339

- рекурсивно перечислимый 140

- рекурсивный 140, 280 Представление Ейтса 169 Примитивная рекурсия 33 Проблема алгоритмическая И

- вхождения 77

- выводимости 319

- Гпльберта (№ 10) 15, 3G3

- делплюсти слева 277

- комбипаторная Поста общая 279 --- ограниченная 279

- конфигураций 312

- нахождения правого обратного элемента 278

- остановки 252, 311, 319

- равенства слов в полугруппах 254

- тождества в теории групп 14

- тождественной истинности формул в исчислении первой ступени, нера!зрешимость 13, 269, 270

Программа 222

- операторного алгоритма 292

- подстановок 228 Продукции однородные 315-

- Поста 284 Прямой пересчет 169

Рекурсия 57

- возвратная 57

- ступени 95

- ограниченная 130

- примитивная 33

- словарная примитивная 210

- совместная 76

Сводимость множеств 156

- табличная 170

Семейство внутренне продукишное 191

- вполне креативное 188 --перечислимое 188

- - рекурсивное 188

- у-перечислиыое 147 Символ индивидуальны11 23

- переменный- 23

- предикатный 264

- предметный 20, 264

--свободны!! 265

--Связанный 265

- функциональный 20, 264

--п-местный 20, 264

Система аксиом выполнимая 268

- множеств креативная 196 -- слабо креативная 197

- подстановок 286

- полу-Туэ 286

- продукций Поста 287

- формальная 284

Слова, графическое равенство 18 Словарная минимизация 211 .- примитивно рекурсивная функция 210 Слово 18 -, вхождение 19 -, длина 18

- машинное 221 -, подстановка 19

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

Слово пустое 18

- расширенное машинное 224

-, результат переработки 226, 289, 292

Состояние внутренней памяти 220

- заключительное 220

- машины 221

- начальное 226

Стандартный номер множества чи-. сел 147

- - функции 154

ТАГ-проблеыа 319 Тезис Тьюринга 45

- Чёрча 12, 44 Теорема Аккермапа 106

- Тёделя 66, 272

- Гильберта - Гёделя 268

- Девиса 330, 343

- Клини о неподвижной точке 137

- Майхила о неподвижной точке 142

- Маркова 129

- Минского 294, 307, 312, 316

- о возвратной рекурсии 58

- о графике частично рекурсивной функции 58

- о мажорируемых неявных функциях 52

- о представлении предикатов 140

- о рекурсии второй ступени 96

- о совместном продолжении 143

- о существовании универсальной функции для одноместных примитивно рекурсивных функций 100

- об изоморфизме нумераций 177

- Патнема 336, 343

- Поста 82

- Поста - Маркова 261

- Поста - Минского 319

- Поста о кванторном представлении 281

- Раиса 138

- Робинсон 10. 109, 343

- Робинсона 69, 75

- Скулема127

Теорема Фридберга 154, 155, 165

- Чёрча 269 Терм 20

- операторный 32

Уравненпе показательное 339

финитное соответствие 178 Формула 266

- второй ступени 276

- Патнема 338

- подстановочная простая 289 --заключительная 289

Формула сигнатуры о 267

- тождественно истинная 267 Функции, равенство 19 Функция Аккермапа 106

- алгоритмически вычислимая (относительно...) 45

- всюду определенная 19

- вычислимая 12

- - по Тьюрингу 226

- - правильно 231

- Гёделя 62

- диофантова 326

-, доопределение 123

- канторовская 60

- Клини универсальная 135

- конечно определённая 154 -, кусочное задание 51

- нигде не определенная 20 -, область определённости 19

- обратная 41

- общерекурсивная 46 --универсальная 100

- показательно диофантова 340

- представляющая 89, 206

- примитивно рекурсивная 35

---относительно <а 35

Функция продуктивная 159

- простейшая 23

- рекурсивная 12

- словарная 206

-- нормально вычислимая 290

--примитивно рекурсивная 210

--простейшая 206, 209

- - частично рекурсивная 206 -, совокушюсть значений 19 -, термальная запись 32

- универсальная 98

- характеристическая 43 --пустого Множества, 43

- частичная 19

- - продуктивная 167

--, расширение 123

--характеристическая 43

- - п-местная 20

- частично рекурсивная 13, 42 --- относительно ® 42

- элементарная (относительно...) 31

--по Кальмару 130

-- по Скулему 131

Эквивалентность 256 - нумерационная 172 Экспонента числа 56 Элементарная теория 267

Ячейка 17, 219 - пустая 17, 219