markov_teorija_algorifmov (Марков - Теория алгоритмов), страница 80

(р.1946) 370, 422 Брауэр (Вгонгчег Е. Е. 3., 188!— 1966) 6, 14, 18, 38, ЗН, 422 Брнттои (Вг)1(оп д. 1..) 370, 422 Бун (Воопе Уч'. Иг., 1920 — !983) 370, 422 Бурсиан В. Р. (! 887 — 1945) 7 Лннннк Ю. В. (19! 5 — 1972) 7, 423 Мальцев А. И. (1909 — 1967) 12, 423 Манин Ю. И. (р, 1937) !2, 423 Марков А. А. (!856 — 1922) 8 Марков А. А. (1903 — 1979) 6 — 9, 1! — 17, 34, 65, 163, 254, 281, 312, 317, 3!8, 343, 344, 350, 368, 369, 383, 385, 394, 396, 401, 415, 418, 422 †4 Мартин-Леф (МагИп-Еб( Р,, р.

1942) 416, 424 Матиясевич Ю, В. (р. 1947) 11, 3!2, 344, 370, 424 Мендельсон (Мепйе!воп Е., р. 193!) !2, 424 Вейль Г. (Твгеу) Н., 1885 — !955) 6 Гейтинг (НеуИпй Л., 1898 — 1980) 38, 3!4, 422 Гедель (бойе! К., 1906 — 1978) 10, !43, 422 Гильберт (НИЬег1 О., Г862 — !943) 9, ! 1, 12, 18, 21, 54, 63, 312, 344, 422 Девис (ОачВ М., р.1928) 11 Детловс В.

К, (р.!923) 12, 20, 144, 422 Драгалии А. Г. (р. !941) 20 Дан (Оейг1 М., 1878 — ! 952) 370, 422 Нагорный Н. М. (р. 1928) 11, 140, 164, 254, 275, 389, 396, 424, 425 Новиков П. С. (190! — 1975) 312„ 329, 344, 370, 425 Жаров В, Г. (р. !950) 17, 163, 282, 296, 422 Орловский Э.

С. (р.1929) 282, 425 Остроухов Д. А. (р.!940) 163, 282, 425 Заславский И. Д. (р. 1932) 20 Плюшкин В. А. (р. !945) 318 Кантор (Сап1ог б., 1845 — 1918) 19 Петер (Ре1ег К., 1905 — 1977) 12, 425 Петри Н. В. (р. 1942) 323, 425 2. Оп сошрц1аЫе пшпЬегв, тчИЬ ап арр1)саИоп (о Гпе Еп(всйе)йнпйвргоЫеш.

А соггес!юп.— Ргос. 1 опйоц МаИЕ Зос., вег. 2, 1937, 43, № 7, р. 544 — 546. Успенский В. Л. 1. Теорема Геделя и теория алгоритмов.— ДАН СССР, 1953, 91, № 4, с. 737 — 740. 2. Лекции о вычнслимых функциях.— Мл Фнзматгиз, 1960. 3. Машина Поста.— Мл Наука, 1979. Успенский В. А. н Семенов А. Л. 1. тчйа! аге 1Ье Га!пв о1 1Ье Гпеогу о1 а!Вогйцшв: Ьамс йече1оршеп1в соппес1ей»ИЬ Гпе сопсер( о1 а!йог!Гпш апй»ИЬ Ив аррйса1юп !п шаИ|ешаИсв,— !п: ЕгвЬоч А. Р., Кга(Ь (7. Е., ейв. А!дог)Иппв !п шойегп ша(Ьешабсв апй согпрн(ег вс1епсе, Зрппйег, !98! (1Н )п согпрц1ег вс(епсе, ч. 122), р. !00 — 234. 2.

Теория алгоритмов; ее основные открытия н приложения.— В кнл Алгоритмы в современной математике и се приложениях, часть 1. Новосибирск, 1982, с. 99 — 342. Нейтнн Г. С. 1. Ассоциативное исчисление с неразрешимой проблемой эквивалентности.— ДАН СССР, 1956, 107, № 3, с. 370 — 371. 2.

Ассоциативное исчисление с неразрешимой проблемой эквивалентности.— Тр. матем. ин-та АН СССР нм. В. А. Стеклова, 52, М.— Лл Изд. АН СССР, !958, с. 172 — 189. 3. Теоремы о среднем значении в конструктивном авализе.— Тр. матем. нн-та АН СССР им. В. А. Стеклова, 87, М.— Лл Изд. АН СССР, 1962, с. 362 — 384. 4. Алгорифмическне операторы в конструктивных метрических пространствах.— Тр.

натем. ин-та АН СССР им. В. А. Стеклова, 67, М.— Лл Изд. АН СССР, !962, с. 295 — 361. 5. Нижняя оценка числа шагов для обращающего нормального алгорифма и других аналогичных алгорифмов.— Зап. научи. семинаров Ленингр. отд. матем. ни-та АН СССР, 1971, 20, с. 243 — 262. Ч е р ч А. (СЬпгсЬ А.) 1. Ап нпво!чаЫе ргоЫсш о1 е1егпеп1агу пнгпЬег 1Ьеогу.— Ашег. Л Ма(Ь., 1936, 58, № 2, р. 345 — 363. 2. А по1е оп (Ье ЕпИсЬе1йнпйвргоЫеш.— Л.

5угпЬо1ге 1ой1с, 1936, 1, р. 40 — 41; СаггесИоп, 1ЬЫ., р. 101 — !02. Шанин Н. А. 1. О конструктивном понимании математических суждений,— Тр. назем, ин-та нм, В. Л. Стеклсва, 52, М.— Лл Изд. ЛН СССР, !958, с. 226 — 3! 1. 2. Конструктивные вещественные числа н конструктивные функциональные пространства.— Тр. мат«м. нн-та АН СССР им. В. А. Стеклова, 67, М.— Лл Изд.

АН СССР, 1962, с. 15 — 294. Ш е н х а!Те А. (Зсйопйайе А.) 1. ()п(чегвеИе Тпппй Зре(сЬегцпд.— !п: Ан(огпа1еп!Ьеопе нпй (оггпа!е 5ргасЬеп. Осгг Л,, Но(х б., ейж МаппЬепп, 1970, 5. 369 — 383. 2. 5(огайе шой(1!са(1оп гпасЫпев.— 51АМ йспгпа! оп согпрцИпй, 1950, 9, № 3, р. 490 — 508. Ш и е к к е р Э. (Зресйег Е.) 1. ЬИсЫ )сопЫгпЫ!ч Ье»еВЬаге 5а)хе йег Лпа!увВ.— Л. ЗугпЬоИс Еод)с, 1949, 14, № 3, 5.

145 — 158. имгмнбй экдздтгль 428 Изоморфнзм 390 Пост (РоЦ Е. 1, 1897 — 1954) 1О, 11, 143, 312, 343, 425 Рабин ()(аЬ!и М. О.„р. 1931) 397, 425 Райс (В!се Н. П.) 338, 339, 425 Рассел (Впазе! В., 1872 — 1970) 304, 3!9 Роджерс (Райегз Н., р. !926) !2, 425 Сеченов Л. 75 (р. !!)50) !2, 420 Сыркин Г. И. (р. !943) 279, 425 Туэ (33ше Л., 1863 — -!922) 11, !2, 343, 425 Тьюринг (ТпПпй А. М., !9!2— !954) 10, 11, 143, 144, 3!2, 398, 425 Успенский В, Л.

(р. !930) !2, 144, 329, 338, 339, 423, 426 Хаусдорф (НаагйогД Е,, 1868— 1942) 19 Хами В. И. (р. 1941) 20 Цейтин Г. С. (р. !936) 163, 334, 369, 412, 415, 417, 426 Цермело (Уегше!о Е., 1871 †19) 304 '!ерч (СЬнгсЬ Л., р. !903) !О, 143, Нз, 31'2, 426 Шанин Н. А. (р. !919) 7, !1, 19, 20, 399, 401, 413, 423, 425, 426 Д1енхаге (5сЬбпЬа8е Л., р. 1944) !44, 426 Шпеккер (5рес)лег Е., р. 1920), 402, 426 Эрбран (НегЬгацб 3,, !907 — 1931 1О Абстрзкция отождес>вхення 35 — потенциальной о уществимастн 34 Алгорифл> 135 — вербальный 136 — — в алфавите !36 — — над алфавитом 137 — двойного проектирования 174, 180 — , его прнменнмасть к исходному данному 136 — нормальный !39 — побунвеннаго кодирования 17! — , результат его работы !36 Ллфавнт 25, 31 Аннулнрующий алгарнфм 150 Арифметическая нндукцня, огрзннченная 83 Арифметические действия над конструктнвнымн действительными числами 412 Ассоциативная система 348 Ассоциативное исчисление 344 — — абелево 393 — — групповое 392 — —, его определяющая система 344 — —, — соотношение 344 — — единичное 392 — — конечное 392 — — палугрупповое 393 — — разрешимое 393 — — , смежность слов в нем 345 — — , эквивалентность слов в нем 345 Атом !08 Бинарное отношение 385 Буква 24 Вербонд 258 Взаимная простота слов 79 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Р ажлезне 94, 97 --, ега левое крыло 97 — , — основа 97 —, — правое крыло 97 — концевое 98 — начальное 98 — первое 1О! Вывод в нсчисленнп 28 — с анализом 29 Высказывание 32 — общности 39 — о существованнн 37 — полуразрешимое 52 — разрешимое 49 Высота слова !74, 372 Вычнслнмая вербальная функцня 330 Вычнслнмый кнваризнт бинарного отношения 385 — оператор над вычислнмыми вербальными функцнямн 336 Гомоморфизм 389 Графическое равенство 29 — различие 29 Двойннк 199 Днэъюнкцня 37 — ее конструктивное пониманне 37 Длина слова 86 Дополнение слова концевое 84 — — начальное 84 Законы сокращения слов 73 Замыкание нормального алгорнфма 197 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 431 Лп-слово 67 Литероид 254 Импликация 43, 54 — дедуктивная Я вЂ” материальная 56 — усиленная 59 Инвариантные свойства ассоциативных исчислений 394 — — — — проблемы распознавания нх 394 — — вычислимых вербальных функций 339 — — — — — нетривиальные 339 Индуктивное определение 28 Индукции по началам слова 82 — — переводной системе 131 — — шагам работы алгорнфмз 132 Интуиционнзм 38 Интуиция общности 40 Исчисление 28 — , его аксиомы 28 — , — правила вывода 28 Итерационная цепь алгорифма 231 Композиция алгорнфмов !98, 217, 335 Конец слова 74 — — собственный 77 Конструктивная действительная функция 400 — — — ее непрерывность 415 — — — — неразрывность 415 — — — , — регулятор непрерывности 415 — математическая логика 38 — последовательность натуральных чисел 399 — — рациональных чисел 399 — — — — ее регулятор сходимости 399 — — — — фундаментальная 399 Конструктивное действительное число 399 — — — его абсолютная величина 413 — — — иррациональное 401 — — — псевдорациональное 401 — — — рациональное 401 Конструктивный объект 23 — — , его построение 29 — — — сугцествоваиие 36 — процесс 23 Кусочное задание конструктивной действительной функции 414 Мажорирование 81, 409 Массовая алгорифмическая проблема 299 Метод деленая отрезка пополам 405, 420 Наибольшее общее начало слов 81 Наследственные свойства ассоциативных исчислений 391 — — — — проблемы распознавания нх 395 Натуральное число 23, 81 Начало слова 74 — — собственное 77 Неотличимость по инвариантам 385 Непустое слово 28 Нормальная массовая проблема 302 — — — разрешимая 302 Нормальный алгорнфм 139 — — , его алфавит !39 — — , — запись 297 — — , — изображение 281 — — — пополнение 323 — —, — сложность 319 — —, — схема 139 — — замкнутый 196 — — несамопрнменимый 303 — — полный 323 — — самопримеиимый 302 Обращающий алгорнфм !66 Обращение слова 69 Объединение алгорифмов 219, 224 335 — алфавитов 73 Оперативная буква 352 Отделимость перечислнмых множеств разрешимыми 328 Отрицание 38, 47 — прямое 49 — — предиката 50 — редукционное 64 — усиленное 53 Оценка сложности нормального алгорнфма верхняя 323 — — — — нижняя 323 Пара слов 93 Парадокс деревенского брадобрея 319 — Рассела 304, 319 Перевод буквы 261 — вхождения 264 — нормального алгорифма 271, 275 — слова 261 — формулы подстановки 270 Переводная система схемы 120 — — — естественная 130 Переменная 44 — вербальная 44 — литеральная 45 — натуральная 44 — предикатная 46 — пропозицвональиая 44 — свободная 44 — связанная 46 Перечислимое множество 312 Повторение алгорифма 230, 245, 247 Подстановка слова вместо вхождения 105 Полная индукция 41 Полугруппа 348 Правило силлогизма 56, 60 — шпана ропепз 43, 56, 59 Предикат 46 — арифметический 101 — вербальный 45 Предшествование вхождений 99 Пример Шпеккера 402 Принцип конструктивного подбора 417 — нормализации !4! †1, !45— 146 Присоединение буквы левое 67 — — правое 31 Присоединяющий алгорифм 146 — — левый 148 — — правый 148 Проблема гомеоморфии полиэдров 17, 312, 344 — нзоморфии 396 — распознавания аннулирования 315 — — несамоприменимости 305 — — применимости 308, 317 — — — ограниченная 321 — — самоприменимости 305 — тождества для групп 312 — — — полугрупп 312, 343, 350 — Туэ 343 — эквивалентности для ассоциативных исчислений 349 Проекция слова на алфавит 88, 173 Пустое слова 25 Пустой алгорифм 148 Равносоставленность алфавитов 31 Развертка разрешимого предиката 90 Разветвление алгорифмов 224, 230 Раззетвляющий алгорнфм 153 Разность алфавитов 73 Разрешимое множество 312 Распространение нормального злгорифма 187 — — — естественное 193 — — — формальное 196 Растягивающий алгорнфм 164 Расширение алфавита 73 Рациональное число 26 — — его действительный образ 401 Рекурсивное определение 69 Семантические соглашения 32 Семиотика 31 Система слов 106 — — ее внутренний член 116 — — , — объем 110 — — , — первый член 110 — — , — последний член 110 — — , — член 110 — — , — элемент 108 — — многочленная 231 — — пустая 110 Слово в алфавите 25, 27, 66 Сложность нормального элгорнфма 1Я Совершенное число 45 Соединение слов 30 Сокращающий алгорифм 144 Схема в алфавите 118 — — — , ее действие на слово 118 Тезис Черча 144 Теорема композиции 198, 217 — Коши о нуле знакопеременной непрерывной функции 414, 419 — о двух концах 7? — — — началах 77 — — наименьшем числе 89 — — неподвижной точке 335, 337 — — непополнимом нормальном алгорифме 324 — об универсальном алгорнфме 281 придмитныт! Укдэдтиль Теорема об универсальном алгорифме видоизмененная 298 — объединения 220, 224 — повторения 231, 245, 247 — приведения 274 — — усиленная 274 †2 Теорема разветвления 225 — Успенского — Райса 339 Тождественный алгорифм 148 Удваиваюший алгорнфм 157 Условное равенство 187 Формула подстановки 1!7 — — , активная на данном слове 117 — — , ее действие !17 — — , — левая часть !!7 — — , — правая часть 117 — — заключительная 117 — — простая 1!7 Характеристический оператор разрешимого преднката 90 Целое число 26 Число шагов работы алгорифма 130 †! Эквивалентность алгорифмов 137— 138 Ядро элемента системы слов 116 Язык, его высказывания, синтаксис и семантика 32 — 33 К-система 348 Т-изоморфизм 397 йебнс!!о аб аЬзпгйнп 64 й-ряд 346 —, его высота и протяжение 372 10-я проблема Гнльберта 312, 344 .