Чарльз Петцольд - Читаем Тьюринга

страницах 84–362 этой книги,
а исправления к ней – на страницах 349–362. Статья Тьюринга делится на 11 разделов (и приложение), которые начинаются на следующих страницах книги:
1. Вычислительные машины
2. Определения
3. Примеры вычислительных машин
4. Сокращенные таблицы
5. Перечисление вычислимых последовательностей
6. Универсальная вычислительная машина
7. Подробное описание универсальной машины
8. Применение диагонального процесса
9. Пространство вычислимых чисел
10. Примеры больших классов вычислимых чисел
11. Применение к Entscheidungsproblem
Приложение

68
72
79
113
131
143
149
173
190
235
260
290

Первоначальным толчком к написанию Тьюрингом этой статьи
было намерение решить задачу, сформулированную немецким математиком Давидом Гильбертом (1862–1943). Гильберта интересовал
общий процесс определения доказуемости произвольных утвержде-

10  Введение
ний в математической логике. Нахождение этого «общего процесса»
было известно как Entscheidungsproblem (с нем. – «решаемость задачи»). Хотя побуждением к написанию статьи для Тьюринга была,
конечно же, Entscheidungsproblem, на деле бо' льшая часть статьи –
о вычислимых числах. По определению Тьюринга, это числа, которые
могут быть вычислены машиной. Исследование вычислимых чисел
составляет первые 60% статьи Тьюринга, которые могут быть прочитаны и поняты без знания работ Гильберта по математической логике
или Entscheidungsproblem.
Различие между вычислимыми числами и «вещественными числами» крайне важно для изложения Тьюринга. По этой причине первые
главы данной книги представляют собой предварительную подготовку к нашей классификации чисел, охватывающей целые числа, рациональные числа, иррациональные числа, алгебраические числа и трансцендентные числа, все из которых относятся также к вещественным
числам. Я старался не полагаться на какие-либо предварительные
знания, более сложные, чем математика средней школы. Понимая, что
некоторых читателей от радостей средней школы могут отделять несколько десятилетий, я попытался освежить эти воспоминания. Прошу простить, если мое педагогическое рвение привело к таким объяснениям, которые унижают или оскорбляют кого-то.
Хотя я подозреваю, что эта книга будет читаться главным образом
специалистами по информатике, программистами и прочими «технарями», я постарался доставить радость и непрограммистам, используя дружелюбный жаргон и терминологию из области искусства.
Статья Тьюринга – это «один из интеллектуальных ориентиров прошедшего столетия»1, и я надеюсь, что данная книга сделает эту статью
доступной еще более широкой аудитории.
Чтобы угодить запросам разных читателей, я поделил эту книгу на
четыре части:
 Часть I («Основы») охватывает исторический и математический фон, который необходим, чтобы приступить к чтению
статьи Тьюринга.
 Часть II («Вычислимые числа») содержит бо' льшую часть
статьи Тьюринга и будет особенно полезна читателям, интересующимся машиной Тьюринга и вопросами вычислимости.
1

John P. Burgess, предисловие к George S. Boolos, John P. Burgess, and Richard
C. Jeffrey, Computability and Logic, fourth edition (Cambridge University Press,
2002), xi.

Введение  11
 Часть III («Entscheidungsproblem») начинается совсем коротким введением в математическую логику и продолжается разбором оставшейся части статьи Тьюринга.
 В части IV («И далее») обсуждается, как случилось, что машина Тьюринга стала важным инструментом для понимания
компьютеров, человеческого сознания и самой вселенной.
Математическое содержание части III, конечно, гораздо сложнее,
чем в предыдущих главах, и излагается в более быстром темпе. Те,
кто не очень интересуется значением статьи Тьюринга для математической логики, могли бы даже при желании пропустить пять глав
части III и перейти сразу к части IV.
Эта книга затрагивает несколько больших разделов математики,
включая вычислимость и математическую логику. Я выбрал и предпочел только наиболее важные для понимания статьи Тьюринга темы
и понятия. Многие детали опущены, и эта книга не заменит глубины
и строгости, которую вы найдете в книгах, специально посвященных
вычислимости и логике. Те читатели, которые намерены глубже покопаться в этих захватывающих областях исследований, могут руководствоваться библиографией.
За всю свою жизнь Алан Тьюринг опубликовал около 30 работ и статей1, но не написал ни одной книги. Две статьи Тьюринга стали причиной его --">