Читать онлайн «Машина Поста»

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ ВЫПУСК 54 В. А. УСПЕНСКИЙ МАШИНА ПОСТА ИЗДАНИЕ ВТОРОЕ, ПЕРЕРАБОТАННОЕ МОСКВА «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1988 ББК 22. 12 У77 УДК 510. 6(023)]! Успенский В. А. •, |У77 Машина Поста. —2-е изд. , испр. — М. : Наука. Гл. ред. физ. -мат. лит. , 1988. — 96 с. — (Попул. лекции по мат. ). ISBN 5-02-013735-9 Машина Поста — это хотя и абстрактная (т. е. не существующая в арсенале действующей техники), но зато очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы. Тем не менее на машине Поста можно запрограммировать — в известном смысле — любые алгоритмы. Изучение машины Поста можно рассматривать как начальный этап обучения теории алгоритмов и программированию. 1-е изд. — 1979 г. Для широкого круга читателей. Ч71702020000—063 пл 00 „„„ лл 1П У 053(02)-88 6°-88 ББК22Л2 Владимир Андреевич Успенский МАШИНА ПОСТА Серия «Популярные лекции по математике», выпуск 54 Редактор В. В. Донченко Художественный редактор Г. Я. Кольченко Технический редактор Л. В. Лихачева Корректоры М. Л\ Медведская, Я. Б. Румянцева ИБ № 32624 Сдано в набор 22. 05. 87. Подписано к печати 12. 01. 88. Формат 84X108/32. Бумага книжно-журнальная. Гарнитура литературная. Печать высокая. Усл. печ. л. 5,04. Усл. кр. -отт. 5,25. Уч. -изд. л. 5,37. Тираж 89 000 экз. Заказ № 595. Цена 20 коп. Ордена Трудового Красного Знамени издательство «Наука» Главная редакция физико-математической литературы 117071 Москва В-71, Ленинский проспект, 15 Ленинградская типография № 2 головное предприятие ордена Трудового Красного Знамени Ленинградского объединения «Техническая книга» им. Евгения Соколовой Союзполиграфпрома при Государственном комитете СССР по делам: издательств» полиграфии и книжной торговли. 198052. г. Ленинград, Л-52, Измайловский проспект, 29. ISBN 5-02-013735-9 © Издательство «Наука». Главная редакция физико-математической литературы, 1979; с изменениями, 1988 ОГЛАВЛЕНИЕ Предисловие *«*... . . « . . . . 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.