В книге на основе понятия нормального алгорифма излагается общая теория алгорифмов и некоторые ее применения. Значительное внимание уделяется логическим и, в частности, семантическим аспектам этой теории. Для математиков, интересующихся основаниями математики, математической логикой и теорией алгорифмов.
Author(s): Марков А.А., Нагорный Н.М.
Series: Математическая логика и основания математики, 25
Publisher: Наука
Year: 1984
Language: Russian
Pages: 433
Предисловие 6
Важнейшие обозначения 22
Глава I. Введение. Основные принципы конструктивной семантики 23
§ 1. Конструктивные процессы и конструктивные объекты 23
§ 2. Слова 26
§ 3. Языки. Высказывания 32
§ 4. Абстракция потенциальной осуществимости 34
§ 5. Абстракция отождествления 35
§ 6. Существование конструктивного, объекта 36
§ 7. Дизъюнкции 37
§ 8. Проблема построения конструктивной математической логики 38
§ 9. Высказывания общности 39
§ 10. Переменные. Предикаты 44
§ 11. Прямое отрицание. Разрешимые высказывания 47
§ 12. Полуразрешимые высказывания. Усиленное отрицание 52
§ 13. Материальная импликация 54
§ 14. Усиленная импликация 58
§ 15. Дедуктивная импликация 61
§ 16. Идея ступенчатой семантической системы 64
Глава II. Семиотика линейно расположенных конструктивных объектов 66
§ 17. Слова (продолжение §2) 66
§ 18. Начала и концы слов 74
§ 19. Длина слова. Проекция слова на алфавит 86
§ 20. Умножение слови на натуральное число 88
§ 21. Теорема о наименьшем числе 89
§ 22. Пары слов 93
§ 23. Вхождения 94
§ 24. Системы слов 106
§ 25. Схемы 116
Глава III. Нормальные алгорифмы: определение и примеры 135
§ 26. Алгорифмы 135
§ 27. Нормальные алгорифмы. Принцип нормализации 138
§ 28. Присоединяющие алгорифмы 146
§ 29. Сокращающие алгорифмы 149
§ 30. Разветвляющий алгорифм 153
§ 31. Удваивающий алгорифм 157
§ 32. Обращающий алгорифм 166
§ 33. Алгорифмы побуквенного кодирования и двойного проектирования 171
§ 34. Некоторые арифметические алгорифмы 180
Глава IV. Сочетания нормальных алгорифмов 187
§ 35. Распространения алгорифма 187
§ 36. Замыкание алгорифма 196
§ 37. Композиция алгорифмов 198
§ 38. Объединение алгорифмов 219
§ 39. Разветвление алгорифмов 224
§ 40. Повторение алгорифма 230
§ 41. Перевод алгорифма 254
Глава V. Универсальный алгорифм 280
§ 42. Формулировка теоремы об универсальном алгорифме . . 280
§ 43. Случай двухбуквенного алфавита 282
§ 44. Доказательство теоремы об универсальном алгорифме . . 291
§ 45. Видоизменение теоремы об универсальном алгорифме . . 296
Глава VI. Основные теоремы невозможности алгорифмов 299
§ 46. Понятие о массовой алгорифмической проблеме 299
§ 47. Самоприменимые и несамоприменимые алгорифмы . . . 302
§ 48. Проблема распознавания применимости алгорифма к исходному данному 308
§ 49. Теоретико-множественный комментарий к §§ 47 и 48 . . . 312
§ 50. Конструктивный комментарий к §§ 47 и 48 313
§ 51. Проблема распознавания аннулирования 315
§ 52. Сложностной подход к проблеме распознавания применимости 317
§ 53. Непополнимый алгорифм 323
Глава VII. Вычислимые вербальные функции 330
§ 54. Вычислимые вербальные функции 330
§ 55. Теорема о неподвижной точке 335
§ 56. Распознавание инвариантных свойств вычислимых вербальных функций 338
Глава VIII. Проблема тождества для полугрупп (проблема Туэ) 343
§ 57. Ассоциативные исчисления 344
§ 58. Построение ассоциативного исчисления с неразрешимой проблемой эквивалентности 350
§ 59. Проблема эквивалентности пустому слову 370
§ 60. Метод вычислимых инвариантов 385
§ 61. Проблемы распознавания свойств ассоциативных исчислений 389
Глава IX. Алгорифмы и математический анализ 398
§ 62. Конструктивные действительные числа и конструктивные действительные функции 399
§ 63. Пример Шнеккера 402
§ 64. Проблема распознавания равенства действительных чисел 405
§ 65. Распознавание мажорирования. Арифметические действия. Кусочное задание функций 410
§ 66. Теорема Коши о нуле знакопеременной непрерывной функции 414
§ 67. Принцип конструктивного подбора 417
§ 68. Теорема Коши о нуле знакопеременной непрерывной функции (продолжение § 66) 419
Литература 422
Именной указатель 427
Предметный указатель 429
