Пиксель. История одной точки

Тьюринг определил, что любая из его машин должна состоять только из четырех элементов: одномерная лента, разделенная на ячейки, ограниченный набор символов для нее, ленточный сканер с ограниченным числом состояний и «таблица инструкций», сообщающая, что делать с каждой комбинацией состояния сканера и символа на ленте. В нашем случает сканирующее устройство — это картонная карточка с отверстием, шесть символов — это цифры от 1 до 5 и пробел, а четыре состояния — это четыре ориентации карты. Четыре набора правил образуют таблицу инструкций. И еще кое-что. Лента должна быть необходимой длины в любом направлении. При необходимости всегда должна найтись еще одна ячейка. Бумаги всегда должно хватать. Возможно, теперь вы понимаете, почему Ньюман поначалу не поверил, что такое простое устройство — на первый взгляд, примитивная игрушка — позволяет получить такой серьезный математический результат. Из этой простой «машинной» концепции произошли все машинные вычисления.

В рассмотренном нами устройстве отражен принцип работы современного компьютера. Сама карточка — это ЦП (центральный процессор), а лента — это память. Но современный компьютер выполнит любое вычисление, если просто изменить программу. Конечно, нашему примитивному устройству из картонной карточки никакие вычисления не под силу, не так ли? А вот и нет! Оно с ними справится! Студия Pixar даже смогла бы сделать с его помощью все необходимые вычисления для «Истории игрушек»! Конечно, пользоваться нашим устройством они бы не стали — это настолько утомительно и медленно, что заняло бы все время существования Вселенной, но скорость — это отдельный вопрос, который мы рассмотрим в следующей главе. Отметим, что наше устройство — это не обычная машина Тьюринга. Машина из картонной карточки — это универсальная машина Тьюринга.

Согласно великой идее Тьюринга, машина Тьюринга не просто выполняет систематический процесс — в ней воплощено то, что мы подразумеваем под «систематическим процессом» или «механистическим процессом». Даже сама по себе идея неплоха. К примеру, таким процессом — как сложить два числа, чтобы получить их сумму, — является алгоритм суммирования. Итак, должна существовать машина Тьюринга, которая «считывает» два числа со своей ленты, складывает их вместе и фиксирует сумму на ленте. И больше ничего не делает.

Другой систематический процесс — переворачивание буквенной строки. Например, если задана строка abcdefg, машина сначала меняет местами крайнюю пару букв, затем следующую и так далее. Процесс продолжается до тех пор, пока не закончатся пары для обмена или не останется только одна буква. В итоге у нас получится gfedcba. Следовательно, существует машина Тьюринга, которая выполняет эту операцию для любой произвольной строки на своей ленте, и ничего больше.

Однако суть идеи Тьюринга заключалась в доказательстве, что одна машина Тьюринга может делать все то же самое, что и любая другая машина Тьюринга. Одна машина способна выполнять все систематические процессы, включая сложение двух чисел или изменение буквенной строки. Это машина, умеющая «вычислять» все, что computable, все, что поддается вычислению, с использованием механистического процесса. В этом и заключается универсальность машинного вычисления. Когда мы говорим, что великой идеей Тьюринга была вычислительная машина, мы имеем в виду универсальную вычислительную машину. Современный компьютер — потомок именно этого типа, универсальной машины Тьюринга. Но как машина Тьюринга может быть универсальной?

Никогда не пытайтесь объяснить устройство компьютера невеждам. Легче девственнице объяснить, что такое секс.

— Роберт А. Хайнлайн. «Луна — суровая хозяйка»

Иди к черту, Хайнлайн! Фокус Тьюринга, позволяющий сделать одну из его машин универсальной, гениален. Машина Тьюринга — это простая вещь, которая определяется набором правил. У нашей машины из картонной карточки, например, есть 24 правила, по 6 для каждого положения. Поэтому Тьюринг предположил, что существует возможность спроектировать машину Тьюринга, которая возьмет описание любой машины Тьюринга, а также входные данные для нее и смоделирует все то, что эта машина будет делать лентой. Он считал это возможным, потому что такое моделирование представляет собой систематический процесс, а машина Тьюринга изобретена для демонстрации исполнения именно того, что мы подразумеваем под систематическим процессом. Машина Тьюринга, которая имитирует любую другую, — это универсальная машина Тьюринга, и Тьюринг показал, как ее сконструировать.