Успенский В. А.

Машина Поста.
М., "Наука" 1988 г., 96 стр.
89 000 экз.

АННОТАЦИЯ

Машина Поста — это хотя и абстрактная (т. е. не существующая в арсенале действующей техники), но зато очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы. Тем не менее на машине Поста можно запрограммировать — в известном смысле — любые алгоритмы. Изучение машины Поста можно рассматривать как начальный этап обучения теории алгоритмов и программированию.

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. Решимые и нерешимые алгоритмические проблемы. В.А. Успенский, А.Л. Семенов


Скачать в формате TIFF 8.0 Mb, в формате DjVu 2.1 Mb

Rambler's Top100

© МЦНМО, 2003
© ФИЗМАТЛИТ, 2003