markov_teorija_algorifmov (Марков - Теория алгоритмов)

математическая логика и основания математики А.А. Марков Н. М. Нагорный ТЕОРИЯ ЛЛГОРИЭМОВ МОСКВА мНАУКА» ГЛАВНАЯ РЕДАКНИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1984 22.12 %20 УДК бру ОГЛАВЛЕНИЕ Предисловие Важнейшие обозначения Андрей Андреевич Марков Николай Макарович Нагорный ТЕОРИЯ АЛГОРИФМОВ ИВ № 12128 66 66 74 86 88 89 93 94 106 116 4 17 4 18 919 820 221 222 923 9 24 826 40 Издательство еНеука, Главная редакция физико.ыатеыеткчеекон литературы, 19н4 1702020000 — ! 44 М 063 !02) 84 — 40 — 84 4е Марков А. А., Нагорный Н. М.

Теория алгорнфмов,— Мл Наука. Главная редакция физико-математической литературы, 1984.— 432 с. В книге на основе понятия нормального алгорнфма излагается общая теория алгорнфмов и некоторые ее применения. Значительное внимание уделяется логическим и, в частности, семантическим аспектам втой теории. Для математиков, интересующихся основаниями математики,матема. тнческой логикой н теорией алгорифмов. Рецензент: доктор физико-математических наук Н.

А. Шанин В, Ю.Н. Гййбййрй 00 Г У Редакторы б. А. Кушнер. и. б. Ленненно Техн. редактор В. Н. Кондакова Корректоры О, А. Сивил, И. Я. Криштель Сдача е яебар 30.03.84. Падяясеяо к цечетн 30.07.84. Формат 84к! 089 . Вуыеге тяп. 701. Литературная гериятуйа. Высокая печать. Уся. печ.

и. 22,79. уел. ко.-отт. 22, 77. уч,-езд л. 24 09. Тираж тооо оке. Зекез№ 2884. цена 3 р. Зо к Иее теаьстео «Неукеь Главная редакция физико-ыетеыаткческой литературы 1 1 707 1 Москва В 7 1, Лепняский проспект, ! В Набрана в Ордена Октябрьской Рееошоцяк я ардена Трудового Красеого зиеыеня Первой Образцовой тяцагрефяв янеки А. А. Жданова Сошзполкгрефороыа пре Гасударственном комитете СССР но делам издательств, иояяграфкя а кикжвой торговле. !!3084 Москва, Вееовее, 28 Отпечатепо во 2.9 типография яздетельстве Наука 121099 Москва, Шубинский пер., 1О Зак. 982 1'лава 1 Введение. Основные принцицы конструктивной семаитнни . 1.

Конструктивные процессы и конструктивные объекты 2. Слова 9 3. Языки. Высказыоаняд 4. Абстракция потенциальной осуществимости . 4 5. Абстракция отождествления .. 4 б. Существование конструктивноги объекта 7, Днзъюнкции .. 8.

Проблема построения конструк!изной математической гики 9. Высказывания общности 9 10. Переменные. Преднклты 2 !1. Прямое отрицание. Разрешимые высказывания 2 12. Полуразрешимые высказывания. Усиленное отрицание 5 !3. Материальная импликация $ !4. Усиленная импликация . 9 15. Дедуктивная нмпликация 9 16. Идея ступенчатой семантическая системы Глава 11 Семиотика линейно расноложеннмх конструктивных объектов Слова (продолжение 42) . Начала н концы слов Длина слова. Проекция слова на алфавит Умножение слова на натуральное число . Теорема о нанл1еньшсы числе Пары слов Вхождения Системы слов . Схемы 26 32 34 ло- 39 44 47 64 61 оглавление О!давление Глава 1П 350 370 385 389 17! 180 Нормальные алгорифмы: определение н примеры 4 26. Алгорифмы 427. Нормальные алгорифмы.

Принцип нормализации . $ 28. Присоединиющие алгорнфмы 929. Сокращающие алгорифмы 4 30. Разаетвляющий алгорифм 6 31. Удваивающий алгорифм 432. Обращающий алгорифм . 9 33. Алгорифмы побуквенного кодирования и двойного проектировавия 934. Некоторые арифметические алгорифмы Глава 1Н Сочетания нормальных алгорнфмов . 4 35. Распространения алгорифма 9 36. Замыкание алгорифма . 437.

Композиция алгорифмов . 938. Обьединение алгорифмов . 4 39. Разветвление алгорифмов . 4 40. Повторение алгорифма $ 41. Перевод алгорифма 135 135 138 Рйб 149 153 157 166 187 187 !96 !9 2!9 224 230 254 1' л а в а Н1!! (1роблема тождества для полугрупп (проблема Туэ) . 9 57. Ассоциативные исчисления, 9 58. Построение ассоциативного исчисления с неразрешньюй проблемой эквивалентности .

й 59. Проблема эквивалентности пустому слову 9 60. Метод вычислимых инвариантов . 4 61. Проблемы распознавания свойств ассоциативных исчисле- ний !"лава !Х Алгорифмы и математический анализ .......... , , 398 й 62. Конструктивные действительные числа н конструктивные действительныс функции . .. , . . .

.. .. .. . 399 й 63. Пример Шпеккера . . .. , 402 9 64. Проблема распознавания равенства действительных чисел 405 6 65. Распознавание мажорирования. Арифметические действия. Кусочное задание функций . ...., . ..,, 410 4 66. Теорема Коши о нуле знакопеременной непрерывной функции 414 й 67. Принцип конструктивного подбора . . .., . . . ..

417 $ 68. Теорема Коши о нуле знакопеременной непрерывной функпии (продолжепие 9 66) . ............... 419 Глава Н Универсальный алгорифм . 942. Формулировка теоремы об универсальном алгорифме 8 43. Случай двухбуквенного алфавита 4 44. Доказательство теоремы об универсальном алгорифме $ 45. Видоизменение теоремы об универсальном алгорифме Литература Именной указатель Предметный указатель 422 427 42с 280 280 282 291 296 299 299 302 308 312 313 315 317 323 Глава ЧП Вычислимые вербальные функции 9 54.

Вычислимые вербальные функции 6 55. Теорема о неподвижной точке . 4 56. Распознавание инвариантных свойств вычислимых вербальных функций 330 330 335 Глава Ч1 Основные теоремм невозможности алгорнфмов 9 46. Понятие о массовой алгорифмической проблеме 947. Самоприменимые и несамоприменимые алгорифмы 948. Проблема распознавания применимости алгорпфма к исходному данному . 9 49.

Теоретико-множественный комментарий к 49 47 и 48 . $ 50. Конструктивный комментарий к 99 47 и 48 9 51. Проблема распознавании аннулирования $ 52. Сложностной подход к проблеме распознавания применимости й 53. Непополиимый алгорифм ПРЕДИСЛОВИЕ Настоящая книга выходит в свет, когда ее главного автора, одного из крупнейших математиков нашего времени Андрея Андреевича Маркова (1903 — 1979) уже иет в живых. По долгу памяти мне, его ученику и соавтору, следовало бы предпослать ей строки, в которых читателю хотя бы вкратце было рассказано о выдающемся вкладе, который А. А.

Марков внес в развитие теории алгорифмов и в создание конструктивной математики. Кроме того, я, вероятно, должен был бы рассказать о его обще- математических взглядах, его творческой манере, о неповторимом своеобразии самой его личности. Однако сделать это нелегко. Тем более — в рамках предисловия к книге. Нелегко уже хотя бы потому, что невозмож. но просто и однозначно отнести деятельность А. А. Маркова к какой-нибудь одной конкретной области науки. Так, будучи математиком, он в последний, математико-логический период своей деятельности, длившийся более тридцати лет, создал собственную концепцию конструктивизма — концепцию, занявшую ныне прочное место в основаниях математики и породившую обширную научную проблематику.

Его взгляды, продолжившие и развившие на современной основе идеи таких блестящих мыслителей, как Л. Э. Я. Брауэр и Г. Вейль, подняли на новую ступень дискуссию об эффективности применяемых в математике средств и позволяют с полным правом охарактеризовать его как глубокого, оригинально мыслящего философа и логика.

В математике тоже невозможно связать деятельность А. А. Маркова с какой-нибудь одной научной дисциплиной. У него можно встретить почти одновременно опубликованные работы по аксиоматической теории множеств и по теории пластичности. Занимаясь тончайшими проблемами конструктивной семантики, он в то же самое время создавал язык для описания Работы вычислительных машин.

Он с пристальным вниманием следил за развитием теоретической кибернетики и внес в этот раздел науки существенный вклад, Он проявлял также живой пРедислОВие интерес к работам по математической экономике и по математической лингвистике, к математической проблематике биологии. Круг занимавших его вопросов был настолько широк, что упоминания о его результатах можно встретить даже в учебниках по геофизике а).

Сегодня большой известностью пользуются ставшие уже классическими работы А. А. Маркова его последнего периода — периода занятий основаниями математики, теорией алгорифмов и математической логикой, Но математики старшего поколения особенно высоко ценят его работы 1940 — 1946 гг. по свободным топологическим группам.

Так, П. С. Александров неоднократно отзывался о них как о лучшем достижении А. А. Маркова в математике. Еще раньше, в начале 30-х годов, А. А. Марков опубликовал серию глубоких работ по общей теории динамических систем. Именно он,— что теперь, к сожалению, знают лишь немногие,— впервые дал независящее от дифференциальных уравнений общее определение динамической системы **). А.

А. Марков оставил непреходящий след во многих областях математики. Но первые опубликованные им циклы работ непосредственно к математике не относились — это были работы по теоретической физике и по небесной механике е**). Кроме того, в ранние студенческие годы, когда А. А. Марков намеревался стать химиком, им были выполнены и опубликованы работы по химии. Обладая огромным собственным научным опытом, А. А.

Марков располагал обширными познаниями в самых разнообразных областях науки. По складу своего ума и по характеру научной деятельности он был, как об этом говорил в своей прощальной речи Н; А. Шанин, естествоиспытателем, и его подход к математике был подходом естествоиспытателя, стремящегося придать развитию теории такое направление, при котором ее результаты имели бы возможно более реальный и огцутимый смысл.

В значительной мере этим н объясняется резкое неприятие А. А. Марковым теории множеств в качестве основы для «) Б у р с и а н В. Р. Теория электромагнитных полей, применяемых в элеитроразвелие. ТЛ. — 2-е изд. — Лл Недра, 1972.(См. с. 178, где излагается рассмотренный А.