Теория вычислений для программистов

Теория вычислений 
для программистов

Том Стюарт

Understanding 
Computation

Tom Stuart

Теория вычислений 
для программистов

Москва, 2023

Том Стюарт

2-е издание, электронное

УДК 004.421.2
ББК 32.973-018
С759

С759
Стюарт, Том.
Теория вычислений для программистов / Т. Стюарт ; пер. с англ. 
А. А. Слинкина. — 2-е изд., эл. — 1 файл pdf : 387 с. — Москва : ДМК Пресс, 
2023. — Систем. требования: Adobe Reader XI либо Adobe Digital Editions 
4.5 ; экран 10". — Текст : электронный.
ISBN 978-5-89818-356-1

Наконец-то появился увлекательный и практичный способ изучать теорию вычислений 
и проектирование языков программирования!
В этой книге теоретическая информатика излагается в хорошо знакомом вам 
контексте, что поможет оценить, почему ее идеи важны и как они отражаются на 
том, чем программист изо дня в день занимается на работе.
Вместо математической нотации или незнакомого академичного языка программирования 
типа Haskell или Lisp в этой книге для объяснения формальной семантики, 
теории автоматов и функционального программирования вкупе с лямбда-исчислением 
применяется язык Ruby, сведенный к минимуму.
Издание предназначено для программистов любой квалификации, знакомых 
хотя бы с одним из современных языков, но не имеющих формальной подготовки в 
информатике.

УДК 004.421.2 
ББК 32.973-018

Электронное издание на основе печатного издания: Теория вычислений для программистов / 
Т. Стюарт ; пер. с англ. А. А. Слинкина. — Москва : ДМК Пресс, 2014. — 384 с. — ISBN 978-5-
94074-979-0. — Текст : непосредственный.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было 
форме и какими бы то ни было средствами без  письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность технических 
ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность 
приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные 
с использованием книги.

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами 
защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.


ISBN 978-5-89818-356-1
© 2013 Tom Stuart
© Оформление, перевод, ДМК Пресс, 2014

Содержание

Предисловие ....................................................................... 10
Для кого предназначена эта книга ........................................... 10
Графические выделения .......................................................... 10
О примерах кода ..................................................................... 11
Как с нами связаться ............................................................... 11
Благодарности ........................................................................ 12

Глава 1. Все, что нужно знать о Ruby ............................. 14
Интерактивная оболочка Ruby ................................................. 14
Значения ................................................................................. 15
Простые данные ................................................................. 15
Структуры данных ................................................................... 16
Процедуры .............................................................................. 17
Поток управления .................................................................... 18
Объекты и методы ................................................................... 18
Классы и модули ..................................................................... 20
Прочее .................................................................................... 21
Локальные переменные и присваивание............................. 22
Строковая интерполяция .................................................... 22
Инспектирование объектов................................................. 22
Печать строк ....................................................................... 23
Методы с переменным числом аргументов ......................... 23
Блоки .................................................................................. 24
Модуль Enumerable ............................................................. 25
Класс Struct ........................................................................ 26
Партизанское латание ........................................................ 27
Определение констант........................................................ 28
Удаление констант .............................................................. 28

Содержание

Часть I. ПРОГРАММЫ И МАШИНЫ ................................. 30
Глава 2. Семантика программ......................................... 32
В чем смысл слова «смысл»? ................................................... 33
Синтаксис ............................................................................... 35
Операционная семантика ........................................................ 36
Семантика мелких шагов ......................................................... 37
Выражения ......................................................................... 39
Предложения ...................................................................... 50
Корректность ...................................................................... 60
Приложения ........................................................................ 61
Семантика крупных шагов ....................................................... 62
Выражения ......................................................................... 63
Предложения ...................................................................... 65
Приложения ........................................................................ 68
Денотационная семантика ...................................................... 70
Выражения ......................................................................... 71
Предложения ...................................................................... 75
Сравнение способов определения семантики .................... 76
Приложения ........................................................................ 77
Формальная семантика на практике ........................................ 79
Формализм ........................................................................ 79
Поиск смысла .......................................................................... 80
Альтернативы ..................................................................... 81
Реализация синтаксических анализаторов .............................. 82

Глава 3. Простейшие компьютеры ................................ 88
Детерминированные конечные автоматы ................................ 88
Состояния, правила и входной поток .................................. 89
Вывод ................................................................................. 90
Детерминированность ........................................................ 91
Моделирование .................................................................. 92
Недетерминированные конечные автоматы ............................ 96
Недетерминированность .................................................... 96
Свободные переходы........................................................ 104
Регулярные выражения ......................................................... 108
Синтаксис ......................................................................... 109
Семантика ........................................................................ 112
Синтаксический анализ .................................................... 122
Эквивалентность ................................................................... 124
Минимизация ДКА ............................................................ 134

Содержание

Глава 4. Кое-что помощнее ........................................... 136

Детерминированные автоматы с магазинной памятью .......... 140
Память .............................................................................. 140
Правила ............................................................................ 142
Детерминированность ...................................................... 144
Моделирование ................................................................ 145
Недетерминированные автоматы с магазинной памятью ...... 152
Моделирование ................................................................ 156
Неэквивалентность ........................................................... 159
Разбор с помощью автоматов с магазинной памятью ............ 160
Лексический анализ ......................................................... 161
Синтаксический анализ .................................................... 163
Применение на практике .................................................. 168
Насколько мощнее? .............................................................. 169

Глава 5. Окончательная машина .................................. 172

Детерминированные машины Тьюринга ................................ 172
Память .............................................................................. 173
Правила ............................................................................ 176
Детерминированность ...................................................... 180
Моделирование ................................................................ 180
Недетерминированные машины Тьюринга ............................ 187
Максимальная мощность ...................................................... 188
Внутренняя память ........................................................... 189
Подпрограммы ................................................................. 192
Несколько лент ................................................................. 194
Многомерная лента .......................................................... 195
Машины общего назначения ................................................. 196
Кодирование .................................................................... 198
Моделирование ................................................................ 200

Часть II. ВЫЧИСЛЕНИЯ И ВЫЧИСЛИМОСТЬ .............. 201

Глава 6. Программирование на пустом месте .......... 203
Имитация лямбда-исчисления .............................................. 204
Работа с процедурами ...................................................... 205
Задача .............................................................................. 207
Числа ................................................................................ 209
Булевы значения ............................................................... 213

Содержание

Предикаты ........................................................................ 217
Пары ................................................................................. 218
Операции над числами ..................................................... 219
Списки .............................................................................. 228
Строки .............................................................................. 231
Решение ........................................................................... 234
Более сложные приемы программирования ..................... 238
Реализация лямбда-исчисления ........................................... 245
Синтаксис ......................................................................... 245
Семантика ........................................................................ 247
Синтаксический разбор .................................................... 253

Глава 7. Универсальность повсюду ............................. 256
Лямбда-исчисление .............................................................. 257
Частично рекурсивные функции ............................................ 260
SKI-исчисление ..................................................................... 266
Iota ........................................................................................ 276
Таг-системы .......................................................................... 280
Циклические таг-системы ..................................................... 289
Игра «Жизнь» Конвея ............................................................. 300
Правило 110 .......................................................................... 303
Вольфрамова 2,3 машина Тьюринга ...................................... 307

Глава 8. Невозможные программы .............................. 308
Факты как они есть ................................................................ 309
Универсальные системы могут выполнять алгоритмы ....... 309
Программы могут замещать машины Тьюринга ................ 313
Код – это данные .............................................................. 314
Универсальные системы могут зацикливаться .................. 316
Программы могут ссылаться сами на себя ........................ 323
Разрешимость ....................................................................... 329
Проблема остановки ............................................................. 331
Построение анализатора остановки ................................. 331
Это никогда работать не будет .......................................... 334
Другие неразрешимые проблемы ......................................... 339
Печальные следствия ............................................................ 342
Почему так происходит? ........................................................ 345
Жизнь в условиях невычислимости ....................................... 346

Содержание

Глава 9. Программирование в игрушечной 
стране ................................................................................. 349
Абстрактная интерпретация .................................................. 350
Планирование маршрута .................................................. 351
Абстракция: умножение знаков ......................................... 352
Аппроксимация и безопасность: сложение знаков ............ 356
Статическая семантика ......................................................... 361
Реализация ....................................................................... 363
Достоинства и ограничения .............................................. 371
Приложения .......................................................................... 374

Послесловие ..................................................................... 376

Предметный указатель ................................................... 378

Предисловие

Для кого предназначена эта книга

Это книга для программистов, интересующихся языками программирования 
и теорией вычислений, в особенности для тех, у кого нет 
формальной подготовки в области математики или информатики.
Если вам интересно расширить кругозор, познакомившись с разделами 
информатики, в которых изучаются программы, языки и 
машины, но пугает математический формализм, часто сопутствующий 
изложению этих тем, то эта книга для вас. Вместо сложной 
нотации мы будем использовать код для объяснения теоретических 
идей, превратив их тем самым в интерактивные инструменты, с которыми 
вы можете экспериментировать в удобном для себя темпе.
Предполагается, что вы знаете хотя бы один современный язык 
программирования, например: Ruby, Python, JavaScript, Java или C#. 
Все примеры написаны на Ruby, но если вы знакомы с любым другим 
языком, то все равно сможете понять код. Однако эта книга не является 
руководством ни по правильному написанию программ на 
Ruby, ни по объектно-ориентированному проектированию. Я стремился, 
чтобы код был кратким и ясным, но необязательно удобным 
для сопровождения; задача состояла в том, чтобы с помощью Ruby 
объяснить информатику, а не наоборот. Это также не учебник и не 
энциклопедия, поэтому вместо формальных рассуждений и строгих 
доказательств я попытаюсь раскрыть некоторые интересные идеи и 
побудить вас к более углубленному изучению.

Графические выделения

В книге применяются следующие графические выделения:
Курсив обозначает новые термины, URL-адреса, адреса электронной 
почты, имена и расширения файлов.

Предисловие

Моноширинный шрифт так набраны листинги программ, а также 
элементы программ внутри основного текста, например, имена переменных 
и функций, типы данных, переменные окружения, предложения 
и ключевые слова языка.
Моноширинный полужирный команды и иной текст, который пользователь 
должен вводить буквально.
Моноширинный курсив текст, вместо которого нужно подставить 
значения, вводимые пользователем или определяемые контекстом.

Таким значком обозначаются советы, предложения и замечания 
общего характера.

Таким значком обозначаются предупреждения и предостережения.


О примерах кода

Эта книга призвана помогать вам в работе. Поэтому вы можете 
использовать приведенный в ней код в собственных программах и 
в документации. Спрашивать у нас разрешение необязательно, если 
только вы не собираетесь воспроизводить значительную часть 
кода. Например, никто не возбраняет включить в свою программу 
несколько фрагментов кода из книги. Однако для продажи или 
распространения примеров на компакт-диске разрешение требуется. 
Цитировать книгу и примеры в ответах на вопросы можно без 
ограничений. Но для включения значительных объемов кода в документацию 
по собственному продукту нужно получить разрешение.
Мы высоко ценим, хотя и не требуем, ссылки на наши издания. 
В ссылке обычно указываются название книги, имя автора, издательство 
и ISBN, например: «Understanding Computation by Tom 
Stuart(O'Reilly). Copyright 2013 Tom Stuart, 978-1-4493-2927-3».
Если вы полагаете, что планируемое использование кода выходит 
за рамки изложенной выше лицензии, пожалуйста, обратитесь к нам 
по адресу permissions@oreilly.com.

Как с нами связаться

Вопросы и замечания по поводу этой книги отправляйте в издательство:

O'Reilly Media, Inc.
1005 Gravenstein Highway North

11

Предисловие

Sebastopol, CA 95472
800-998-9938 (в США или Канаде)
707-829-0515 (международный или местный)
707-829-0104 (факс)
Для этой книги имеется веб-страница, на которой выкладываются 
списки замеченных ошибок, примеры и разного рода дополнительная 
информация. Адрес страницы: 

http://oreil.ly/understanding-computation
Замечания и вопросы технического характера следует отправлять 
по адресу:

bookquestions@oreilly.com
Дополнительную информацию о наших книгах, конференциях, 
ресурсных центрах и сети O'Reilly Network можно найти по на сайте:

http://www.oreilly.com

Ищите нас на Facebook: http://facebook.com/oreilly.

Следуйте за нами на Twitter: http://twitter.com/oreillymedia.

Смотрите нас на YouTube: http://www.youtube.com/oreillymedia.

Благодарности

Я благодарен за гостеприимство компании Go Free Range, которая 
предоставила мне на время написания этой книги место в офисе, 
чашку чая и дружескую беседу. Без ее щедрой поддержки я бы точно 
пошел по стопам Джека Торренса1.
Спасибо вам, Джеймс Адам (James Adam), Пол Баттли (Paul 
Batt ley), Джеймс Коглан (James Coglan), Питер Флетчер (Peter 
Fletcher), Крис Лоуис (Chris Lowis) и Маррей Стил (Murray Steele), 
за отзывы на черновики и вам, Габриэль Кернейс (Gabriel Ker-
neis) и Алекс Стэнгл,  за технические рецензии. Благодаря вашим 
глубоким замечаниям книга стала неизмеримо лучше. Хочу также 
поблагодарить Алана Майкрофта (Alan Mycroft) из Кэмбриджского 
университета  за знания, которыми он щедро делился, и за ободрение.
Многие сотрудники издательства O'Reilly помогали довести этот 
проект до завершения, но особенно я благодарен Майку Лоукидесу 
(Mike Loukides) и Саймону Сен-Лорану (Simon St.Laurent) за 

12

1 Персонаж романа «Сияние» Стивена Кинга и одноименного фильма 
с Джеком Николсоном в главной роли. – Прим. перев.

Предисловие

энту зиазм на ранних этапах и веру в идею, Натану Джепсону (Na-
than Jepson) за совет о том, как сделать из идеи книгу, и Сандерсу 
Клейнфельду (Sanders Kleinfeld), который с юмором относился 
к моим неустанным попыткам научиться правильно расставлять 
знаки препинания.
Спасибо моим родителям, которые дали неугомонному дитяти 
возможность и подтолкнули его тратить все свое время на возню 
с компьютерами. И еще Лейле, которая напоминала, как низать 
на строчки чертовы слова, всякий раз, когда я забывал о работе. 
В конце концов я все-таки добрался до конца.

Глава 1. Все, что нужно знать 
о Ruby

Код в этой книге написан на Ruby, языке программирования, который 
был задуман простым и дружелюбным, чтобы работа с ним 
доставляла удовольствие. Я выбрал его за ясность и гибкость, но 
ничто в этой книге не зависит от особенностей, присущих только 
Ruby, поэтому можете переписать примеры на своем любимом языке, 
особенно если он динамический, как Python или JavaScript, – 
если это поможет усвоению идей.
Все примеры совместимы с версиями Ruby 2.0 и Ruby 1.9. Получить 
дополнительные сведения о Ruby и скачать официальную документацию 
можно на сайте Ruby по адресу http://www.ruby-lang.org.
Сейчас мы совершим небольшой экскурс в возможности Ruby. 
Нас будут интересовать в первую очередь те части языка, которые 
используются в этой книге; если хотите узнать больше, начните 
с книги «The Ruby Programming Language», вышедшей в издательстве 
O'Reilly1.

 Если вы уже знакомы с Ruby, можете, не опасаясь что-то пропустить, 
сразу переходить к главе 2.

Интерактивная оболочка Ruby

Одна из самых удобных черт Ruby – его интерактивная консоль 
IRB  , которая позволяет вводить код и сразу же видеть результат его 
выполнения. В этой книге мы постоянно будем использовать IRB, 
чтобы интерактивно исследовать, как работает наш код.

1 Д. Флэнаган, Ю. Мацумото. Язык программирования Ruby. – Питер, 
2011. – Прим. перев.

Для запуска IRB на своей машине введите в командной строке 
слово irb. IRB выводит приглашение  >>, когда ожидает ввод выражения 
Ruby. После того как вы введете выражение и нажмете клавишу 
Enter, код будет выполнен, и на экране появится результат 
после знака => :

$ irb --simple-prompt
>> 1 + 2
=> 3
>> 'hello world'.length
=> 11

Встретив в книге приглашения >> и =>, знайте, что мы работаем 
с IRB. Чтобы длинные листинги было проще читать, мы показываем 
их без приглашений, но при этом предполагаем, что содержащийся 
в них код будет набран или скопирован в IRB. Так что, если в книге 
встречается код типа…

x = 2
y = 3
z = x + y

…то можно воспользоваться результатами его выполнения в IRB:

>> x * y * z
=> 30

Значения

 Ruby – язык, ориентированный на выражения: любой допустимый 
фрагмент кода порождает при выполнении значение. Ниже 
дается краткий обзор различных видов значений в Ruby.

Простые данные

 Как и следовало ожидать, Ruby поддерживает булевы значения, 
числа и строки, а также стандартные операции над ними:

>> (true && false) || true
=> true
>> (3 + 3) * (14 / 2)
=> 42
>> 'hello' + ' world'
=> "hello world"
>> 'hello world'.slice(6)
=> "w"

Значения