Успенский В. А.
Машина Поста. АННОТАЦИЯ
Машина Поста — это хотя и абстрактная (т. е. не
существующая в арсенале действующей техники), но зато очень простая
вычислительная машина. Она способна выполнять лишь самые элементарные
действия, и потому ее описание и составление простейших программ может
быть доступно ученикам начальной школы. Тем не менее на машине Поста
можно запрограммировать — в известном смысле — любые алгоритмы. Изучение
машины Поста можно рассматривать как начальный этап обучения теории
алгоритмов и программированию. 1-е изд. — 1979 г. Для широкого круга читателей. СОДЕРЖАНИЕ
Предисловие
Глава первая КАК РАБОТАЕТ МАШИНА ПОСТА
§ 1. "Внешний вид" машины Поста
§ 2. Программа машины Поста
§ 3. Работа машины Поста
§ 4. Примеры выполнения программ
§ 5. Методические замечания
Глава вторая ПРИБАВЛЕНИЕ ЕДИНИЦЫ НА МАШИНЕ ПОСТА
§ 1. Запись чисел в машине Поста и постановка задачи о прибавлении единицы
§ 2. Прибавление единицы в простейшем случае
§ 3, Прибавление единицы в более сложных случаях
§ 4. Прибавление единицы в еще более сложном случае
§ 5. Прибавление единицы в самом общем случае
Глава третья АНАЛИЗ И СИНТЕЗ ПРОГРАММ МАШИНЫ ПОСТА
§ 1. Диаграммы и блок-схемы
§ 2. Анализ программы прибавления единицы
§ 3. Еще о задаче прибавления единицы
§ 4. Сложение чисел в простых случаях
§ 5. Сложение чисел в более сложных случаях
Глава четвертая ВОЗМОЖНОСТИ МАШИНЫ ПОСТА
§ 1. О задаче сложения чисел на произвольных расстояниях
§ 2. Предложение (постулат) Поста
§ 3. Машина Поста и алгоритмы
§ 4. Вычислимые функции и тезис Поста
§ 5. Машина Поста и электронные вычислительные машины
Приложение 1. Финитные комбинаторные процессы, формулировка 1. Эмиль Л. Пост
Приложение 2. Решимые и нерешимые алгоритмические проблемы. В.А. Успенский, А.Л. Семенов
© МЦНМО, 2003
М., "Наука" 1988 г., 96 стр.
89 000 экз.
© ФИЗМАТЛИТ, 2003