Предисловие (ко второму изданию) Глава первая КАК РАБОТАЕТ МАШИНА ПОСТА § 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 ![]() Доктор физико-математических наук, профессор. Заведующий кафедрой математической логики и теории алгоритмов механико-математического факультета Московского государственного университета имени М. В. Ломоносова. Окончил механико-математический факультет МГУ в 1952 г.; ученик великого математика А. Н. Колмогорова. Один из организаторов отделения структурной и прикладной лингвистики (ныне отделение теоретической и прикладной лингвистики) филологического факультета МГУ. Инициатор реформы лингвистического образования в России. Автор научных работ в области теории алгоритмов и лингвистики, а также художественных произведений в жанре мемуарной прозы. Подготовил 25 кандидатов и 4 докторов наук. За книгу «Апология математики» получил главный приз премии «Просветитель» в 2010 году в области естественных и точных наук.
|