Машина Поста.

Владимир Андреевич Успенский

М.: Наука, 1988. 98 с.
Тираж 89000 экз.
Серия Популярные лекции по математике, выпуск 54

Загрузить (Mb) djvu (1.81) pdf (-) ps (-) html (-) tex (-)

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

---

Содержание

Предисловие

Глава первая. КАК РАБОТАЕТ МАШИНА ПОСТА
    § 1. "Внешний вид" машины Поста
    § 2. Программа машины Поста
    § 3. Работа машины Поста
    § 4. Примеры выполнения программ
    § 5. Методические замечания

Глава вторая. ПРИБАВЛЕНИЕ ЕДИНИЦЫ НА МАШИНЕ ПОСТА
    § 1. Запись чисел в машине Поста и постановка задачи о прибавлении единицы
    § 2. Прибавление единицы в простейшем случае
    § 3. Прибавление единицы в более сложных случаях
    § 4. Прибавление единицы в еще более сложном случае
    § 5. Прибавление единицы в самом общем случае

Глава третья. АНАЛИЗ И СИНТЕЗ ПРОГРАММ МАШИНЫ ПОСТА
    § 1. Диаграммы и блок-схемы
    § 2. Анализ программы прибавления единицы
    § 3. Еще о задаче прибавления единицы
    § 4. Сложение чисел в простых случаях
    § 5. Сложение чисел в более сложных случаях

Глава четвертая. ВОЗМОЖНОСТИ МАШИНЫ ПОСТА
    § 1. О задаче сложения чисел на произвольных расстояниях
    § 2. Предложение (постулат) Поста
    § 3. Машина Поста и алгоритмы
    § 4. Вычислимые функции и тезис Поста
    § 5. Машина Поста и электронные вычислительные машины

Приложение 1. Финитные комбинаторные процессы, формулировка 1. Эмиль Л. Пост

Приложение 2. Решимые и нерешимые алгоритмические проблемы. В.А. Успенский, А.Л. Семенов

---

Загрузить (Mb) djvu (1.81) pdf (-) ps (-) html (-) tex (-)