Math.ru Библиотека

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

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

М.: Наука, 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 (-)