Читаем Тьюринга [Чарльз Петцольд] (pdf) читать постранично, страница - 2

выговорить без запинки это слово, сделав
ударение на втором слоге и произнеся его как «шай», и знаете, что
оно значит («проблема разрешимости»), у вас все же остается подозрение, что Тьюринг предполагает предварительное знакомство своего читателя с трудными немецкими математическими рукописями.
Беглый просмотр статьи, где для обозначения состояний машины используется готический шрифт, отнюдь не помогает унять эти страхи.
Так может ли читатель в наши дни взяться за статью, опубликованную 70 лет назад в Трудах Лондонского математического общества,
и остаться на плаву достаточно долго, чтобы в полной мере проникнуться ею и, возможно, даже получить от нее удовольствие?

8

 Введение

Обо всем этом – наша книга. Она содержит оригинальную 36-страничную статью Тьюринга «О вычислимых числах применительно к
Entscheidungsproblem»1 и последующие трехстраничные Исправления2, а также вспомогательные главы и развернутые комментарии.
Чтение оригинальной статьи Тьюринга – это уникальное путешествие в его изобретательный и захватывающий образ мыслей, когда
он создает машину, которая имела такие далеко идущие последствия
для вычислений и, больше того, для нашего понимания ограничений
математики, человеческого мышления и, возможно даже, природы
вселенной. (Конечно, самого термина «машина Тьюринга» в статье
Тьюринга нет. Он назвал ее «вычислительной машиной». Но термин
«машина Тьюринга» использовался уже с начала 1937 года3 и с тех
пор остается общепринятым.) В своих комментариях к статье Тьюринга я счел полезным часто прерывать его изложение своими пояснениями и уточнениями. Я пытался (не всегда успешно) не прерывать его посреди предложения. В большей части своих объяснений я
сохранял терминологию и систему обозначений самого Тьюринга, но
время от времени ощущал необходимость ввести термины, которые
Тьюринг не использует, но которые я счел полезными при объяснении его работы.
Текст статьи Тьюринга выделяется затененным фоном:
Мы избежим путаницы, говоря чаще о вычислимых последовательностях, нежели о вычислимых числах.
Мы (то есть мой издатель и я) попытались сохранить типографский набор и верстку оригинальной статьи, за исключением некоторых причуд (таких, как пробелы перед двоеточиями), которые вызывали «панику» в современных текстовых редакторах. Сохранены
все оригинальные разрывы строк. В статье Тьюринга есть несколько
опечаток, ошибок и пропусков. Они оставлены без изменений, но
я обращаю на них внимание в своих комментариях. Тьюринг часто
1

2

3

Turing А. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2nd series, Vol. 42
(1936), pp. 230–265.
Turing А. On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction, Proceedings of the London Mathematical Society,
2nd series, Vol. 43 (1937), pp. 544–546.
Alonzo Church, review of «On Computable Numbers, with an Application to
the Entscheidungsproblem», The Journal of Symbolic Logic, Vol. 2, No. 1 (Mar.
1937), 42–43.

Введение  9
ссылается на предыдущие части своей статьи путем указания номера страницы оригинала в журнале. Я оставил эти ссылки в покое,
но снабдил свои комментарии подсказкой для поиска определенной
страницы в этой книге. Иногда в тексте Тьюринга вы увидите номер
в квадратных скобках:
Если буквы заменить числами, как в §5, мы получим числовое
[243]
описание полной конфигурации, которое можно назвать ее описательным номером.
Это – конец одной и начало следующей страницы оригинала с ее
номером. Мои сноски – номерные; сноски Тьюринга – символьные и
тоже оттенены фоном. Если вы удалите страницы этой книги, вырезав и
выбросив все, что не затенено, а потом склеите вместе остатки, у вас получится полная статья Тьюринга и один несчастный автор. Но гораздо
интереснее, наверное, сначала прочитать эту книгу, а потом вернуться
назад и прочитать саму статью Тьюринга без моих грубых вмешательств.
Статья Тьюринга расположена на страницах 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 (с нем. – «решаемость задачи»). Хотя побуждением к написанию статьи для Тьюринга была,
конечно же,