"Популярные лекции по математике", выпуск 54. Машина Поста

Автор(ы):Успенский В. А.
07.07.2008
Описание: Машина Поста — это хотя и абстрактная (т. е. не существующая в арсенале действующей техники), но зато очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы. Тем не менее на машине Поста можно запрограммировать — в известном смысле — любые алгоритмы. Изучение машины Поста можно рассматривать как начальный этап обучения теории алгоритмов и программированию.
Оглавление: Предисловие [4]
Глава первая. КАК РАБОТАЕТ МАШИНА ПОСТА
  § 1. «Внешний вид» машины Поста [7]
  § 2. Программа машины Поста [10]
  § 3. Работа машины Поста [12]
  § 4. Примеры выполнения программ [14]
  § 5. Методические замечания [17]
Глава вторая. ПРИБАВЛЕНИЕ ЕДИНИЦЫ НА МАШИНЕ ПОСТА
  § 1. Запись чисел в машине Поста и постановка задачи о прибавлении единицы [22]
  § 2. Прибавление единицы в простейшем случае [24]
  § 3. Прибавление единицы в более сложных случаях [27]
  § 4. Прибавление единицы в еще более сложном случае [31]
  § 5. Прибавление единицы в самом общем случае [36]
Глава третья. АНАЛИЗ И СИНТЕЗ ПРОГРАММ МАШИНЫ ПОСТА
  § 1. Диаграммы и блок-схемы [37]
  § 2. Анализ программы прибавления единицы [41]
  § 3. Еще о задаче прибавления единицы [46]
  § 4. Сложение чисел в простых случаях [50]
  § 5. Сложение чисел в более сложных случаях [55]
Глава четвертая. ВОЗМОЖНОСТИ МАШИНЫ ПОСТА
  § 1. О задаче сложения чисел на произвольных расстояниях [58]
  § 2. Предложение (постулат) Поста [61]
  § 3. Машина Поста и алгоритмы [66]
  § 4. Вычислимые функции и тезис Поста [71]
  § 5. Машина Поста и электронные вычислительные машины [77]
Приложение 1. Финитные комбинаторные процессы, формулировка 1. Эмиль Л. Пост [83]
Приложение 2. Решимые и нерешимые алгоритмические проблемы. В. А. Успенский, Л, Л. Семенов [89]
Формат: djvu
Размер:1901748 байт
Язык:РУС
Рейтинг: 177 Рейтинг
Открыть: