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

Эта книга, являющаяся введением в теорию алгоритмов, посвящена разъяснению одного из самых основных понятий математики — понятия алгоритма; в ней рассматривается круг вопросов, лежащих на грани между математической логикой и теорией автоматических вычислительных машин.

Книга состоит из трёх почти равных по объёму частей. Первая часть, «Алгоритмы» (§ 1—6), ещё не относится к теории алгоритмов, хотя в ней сплошь и рядом идёт речь об алгоритмах. Дело в том, что здесь слово «алгоритм» понимается в интуитивном смысле; теория же начинается лишь там, где термин обозначает уже точно определяемое математическое понятие. Тем не менее материал этой части, носящий подготовительный характер, весьма важен и полезен для понимания содержательных стимулов в пользу теории.

Вторая часть, «Машины Тьюринга» (§ 7—13), вводит уже непосредственно в круг основных понятий теории алгоритмов.

Третья часть, «Алгоритмические проблемы» (§ 14—23), является кульминационной. В ней излагается ряд фундаментальных результатов теории, которые, к счастью, поддаются популяризации. Более подробная характеристика содержания книги дана во введении.

Несколько слов нужно сказать о происхождении книги.

Начальным стимулом к популяризации теории алгоритмов в печати явились для автора трудности и огорчения, которые он испытывал при первых попытках устной её популяризации. Это случилось более 20 лет назад, когда автор выступил на эту тему перед своими коллегами — математиками Пензенского педагогического института. Такие идеи и результаты теории алгоритмов, как формализация вычислительного процесса, существование неразрешимых алгоритмических проблем выглядели тогда не только непривычными, но и отпугивающими.

Написание популярной статьи или небольшой книги, в которой читатель кратчайшим путём мог бы дойти до теорем об алгоритмической неразрешимости, представлялось тогда автору неотложным делом.

В результате этого появилась статья «Алгоритмы и машинное решение задач» («Математика в школе», 1956, № 4— 5); её расширенные варианты были изданы дважды (Гостехиздат, 1957 г.; Физматгиз, 1960 г.) в виде одноимённой книги, переведённой и на ряд иностранных языков.

Параграфы 1—9 и 13—16 настоящей книги целиком включают содержание упомянутых выше публикаций, которые подверглись тщательному просмотру и переработке.

Кроме того, книга содержит довольно обширный новый материал, а именно § 10—12 и § 17—24, в основу которых легли лекции, прочитанные автором студентам отделения математической лингвистики и слушателям факультета повышения квалификации Новосибирского университета. Этот материал представляет, как нам кажется, большой интерес для понимания таких разделов теории алгоритмов, которые уже не связаны непосредственно с явлением алгоритмической неразрешимости. Здесь имеются в виду главным образом следующие три проблемы: программирование (§ 10—12), качество алгоритмов (§ 17—20) и автоматы параллельного действия (§ 21—23). Впрочем, часть этого материала невозможно было включить в предыдущие издания потому, что он касается новых результатов, появившихся сравнительно недавно…

ПРЕДИСЛОВИЕ
Б. Трахтенброт
Новосибирск, Академгородок, ноябрь, 1973 г.

Предисловие	3
Введение	5

ЧАСТЬ I. Алгоритмы	11

§ 1. Численные алгоритмы	11
1.1. Арифметические действия; алгоритм Евклида	11
1.2. Численные алгоритмы	13
1.3. Диофантовы уравнения	14
§ 2. Алгоритмы игр	15
2.1. Одиннадцать предметов	16
2.2. Побеждает чёт	17
2.3. Дерево игры	17
2.4. Существование выигрышной стратегии	20
§ 3. Алгоритмы поиска пути в лабиринте	25
3.1. Лабиринты	25
3.2. Алгоритм поиска	26
3.3. Обоснование алгоритма поиска	29
§ 4. Проблема слов	33
4.1. Ассоциативные исчисления	33
4.2. Проблема эквивалентности слов	34
4.3. Проблема слов и лабиринты	36
4.4. Построение алгоритмов	37
4.5. Самосовмещения квадрата	42
4.6. Уравнения в словах	46
§ 5. Вычислительная машина с автоматическим управлением	46
5.1. Человек-вычислитель	46
5.2. Вычислительные машины	48
5.3. Машинные команды	50
§ 6. Программа (машинный алгоритм)	52
6.1. Программа для линейных уравнений	53
6.2. Повторение	54
6.3. Программирование алгоритма Евклида	57
6.4. Функционирование вычислительной машины	58
6.5. Другие применения вычислительных машин	59

ЧАСТЬ II. Машины Тьюринга	60

§ 7. Необходимость уточнения понятия алгоритма	60
7.1. Существование алгоритмов	60
7.2. Распознавание выводимости	63
7.3. Формулировка определения «алгоритма»	65
§ 8. Машина Тьюринга	68
8.1. Определение машины Тьюринга	68
8.2. Функционирование машины Тьюринга	73
§ 9. Реализация алгоритма в машине Тьюринга (тьюрингово вычисление)	76
9.1. Переход от n к n + 1 в десятичной системе счисления	76
9.2. Перевод унарной записи в десятичную	79
9.3. Сложение	81
9.4. Повторное суммирование и умножение	82
9.5. Нахождение общего наибольшего делителя	84
§ 10. Программирующие алгоритмы	88
10.1. Стандартные программы и формальные операции над программами	88
10.2. Последовательная композиция	91
10.3. Параллельная композиция	93
10.4. Разветвление алгоритмов	94
10.5. Повторное применение алгоритма	96
10.6. Языки программирования	98
§ 11. Рекурсивные функции и функции, вычислимые по Тьюрингу	99
11.1. Вычисление функций и алгоритмические проблемы	99
11.2. Простейшие операторы	102
11.3. Примитивная рекурсия	103
11.4. μ-оператор	107
11.5. Рекурсивные описания и их тьюрингово программирование	108
11.6. Рекурсивное программирование функций, вычислимых по
Тьюрингу	112
§ 12. Варианты внешней памяти	115
12.1. Полуленты и параллельная композиция	116
12.2. Доказательство теоремы о полуленте	117
12.3. Многоэтажные и многомерные ленты	119
§ 13. Основная гипотеза теории алгоритмов	120
13.1. Гипотеза и её значение	120
13.2. Обоснование гипотезы	123

ЧACTb III. Алгоритмические проблемы	125

§ 14. Универсальная машина Тьюринга	125
14.1. Алгоритм подражания	125
14.2. Универсальная машина	127
§ 15. Алгоритмически неразрешимые проблемы	131
15.1. Теорема Черча	131
15.2. Распознавание самоприменимости и переводимости	132
15.3. Краткий исторический обзор	134
§ 16. Невозможность алгоритма для проблемы эквивалентности слов	138
16.1. Невозможность алгоритма распознавания переводимости слов	138
16.2. Неразрешимость проблемы эквивалентности	143
§ 17. Качество алгоритмов и вычислений	144
17.1. Сигнализирующие функции	144
17.2. Оценки для примеров § 9	145
17.3. Поиск лучшего алгоритма	146
17.4. Распознавание симметрии	148
§ 18. Следы тьюринговых вычислений	150
18.1. Следы	150
18.2. Эксперимент с разрезанной лентой	152
18.3. Замещения	152
§ 19. Нижние оценки сложности	153
19.1. Сложность распознавания симметрии	153
19.2. Сложность перевода в десятичную запись	155
§ 20. Существование сколь угодно сложных проблем	156
20.1. Уточнение постановки вопроса	157
20.2. Распознавание f-самоприменимости	158
§ 21. Автоматы Неймана	161
21.1. Системы тьюринговых машин	161
21.5. Автоматы Неймана	163
21.3. Пример: неймановы часы	166
21.4. Нейманово моделирование машин Тьюринга	167
§ 22. Задача о стрелках	172
22.1. Стрелки	172
22.2. Стрелки и автоматы	173
22.3. Решение задачи	176
§ 23. Сравнение неймановых и тьюринговых вычислений	179
23.1. Кодирование	179
23.2. Вычислимость по Нейману и по Тьюрингу	182
23.3. Распознавание симметрии на автомате Неймана	185
23.4. Тьюрингово моделирование автомата Неймана	188
§ 24 заключительный	190

Указатель	195
Содержание	198

Книги на ту же тему

Ориентированные графы и конечные автоматы, Мелихов А. Н., 1971
Основы кибернетики, Джордж Ф., 1984
Машины Тьюринга и рекурсивные функции, Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г., 1972
Булева алгебра и конечные автоматы, Кунцман Ж., Наслен П., ред., 1969
Теория алгоритмов: основные открытия и приложения, Успенский В. А., Семёнов А. Л., 1987
Машины клеточных автоматов, Тоффоли Т., Марголус Н., 1991
Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
Арифметика. Алгоритмы. Сложность вычислений: Популярное введение в теорию чисел и арифметическую теорию сложности, Гашков С. Б., Чубариков В. Н., 1996
Задачи по теории множеств, математической логике и теории алгоритмов, Лавров И. А., Максимова Л. Л., 1975
Анализ алгоритмов. Вводный курс, Макконнелл Д., 2002
Введение в дискретную математику, Яблонский С. В., 1979
Эволюционная кибернетика, Редько В. Г., 2001
Бионика, Жерарден Л., 1971
Адаптация и обучение в автоматических системах, Цыпкин Я. З., 1968
Нечёткие множества в моделях управления и искусственного интеллекта, Аверкин А. Н., Батыршин И. 3., Блишун А. Ф., Силов В. Б., Тарасов В. Б., 1986
Кибернетика, или управление и связь в животном и машине, Винер Н., 1958

elapsed time 0.019 sec

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему