URSS.ru Магазин научной книги
Обложка Успенский В.А. Машина Поста Обложка Успенский В.А. Машина Поста
Id: 115901
451 р.

Машина Поста № 101. Изд. 3

2021. 104 с.
Типографская бумага

Аннотация

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


Оглавление
top
Предисловие (ко второму изданию)
Глава первая
КАК РАБОТАЕТ МАШИНА ПОСТА
§ 1. «Внешний вид» машины Поста
§ 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

Об авторе
top
photoУспенский Владимир Андреевич
Доктор физико-математических наук, профессор. Заведующий кафедрой математической логики и теории алгоритмов механико-математического факультета Московского государственного университета имени М. В. Ломоносова. Окончил механико-математический факультет МГУ в 1952 г.; ученик великого математика А. Н. Колмогорова. Один из организаторов отделения структурной и прикладной лингвистики (ныне отделение теоретической и прикладной лингвистики) филологического факультета МГУ. Инициатор реформы лингвистического образования в России. Автор научных работ в области теории алгоритмов и лингвистики, а также художественных произведений в жанре мемуарной прозы. Подготовил 25 кандидатов и 4 докторов наук. За книгу «Апология математики» получил главный приз премии «Просветитель» в 2010 году в области естественных и точных наук.