Но она не передавала всю утомительность их труда. Утомление возникает — как вы уже догадались, если следовали приведенным выше инструкциям, — из-за непрерывно повторяющихся примитивных шагов, постоянного беспокойства из-за возможности ошибиться и усилий по сохранению в памяти текущего положения — скажем, во время перерыва на чай. Не отражала модель и того, насколько скучна подобная работа. Вспомните, как говорила Ханна у Стоппарда: «Ты хочешь сказать, что проблема только в этом? В скуке? Валентайн! Проблема только в этом?» Машина не устает и не скучает. С такими проблемами сталкивается лишь человек. Тьюринг создал абстрактную модель значимых действий «вычислителя». Он абстрагировался от утомительности и от скуки как от несущественных категорий. Он использовал такие понятия, как различные состояния ума, пошаговые инструкции, написание и стирание символов и бесконечный запас бумаги для записей.
Есть четыре возможных положения, которые принимает карточка, и есть шесть символов (считая пробел). Соответственно, существует шесть правил для каждого положения карты, по одному для каждого символа, который может появиться в окошке. Общее правило действий заключается в том, что на каждом шаге символ в окошке может измениться, сама карта — переместиться влево или вправо на одну клетку и принять другое положение. А еще дальнейшие действия могут просто прекратиться. Вот и все.
Тьюринг определил, что любая из его машин должна состоять только из четырех элементов: одномерная лента, разделенная на ячейки, ограниченный набор символов для нее, ленточный сканер с ограниченным числом состояний и «таблица инструкций», сообщающая, что делать с каждой комбинацией состояния сканера и символа на ленте. В нашем случает сканирующее устройство — это картонная карточка с отверстием, шесть символов — это цифры от 1 до 5 и пробел, а четыре состояния — это четыре ориентации карты. Четыре набора правил образуют таблицу инструкций. И еще кое-что. Лента должна быть необходимой длины в любом направлении. При необходимости всегда должна найтись еще одна ячейка. Бумаги всегда должно хватать. Возможно, теперь вы понимаете, почему Ньюман поначалу не поверил, что такое простое устройство — на первый взгляд, примитивная игрушка — позволяет получить такой серьезный математический результат. Из этой простой «машинной» концепции произошли все машинные вычисления.
В рассмотренном нами устройстве отражен принцип работы современного компьютера. Сама карточка — это ЦП (центральный процессор), а лента — это память. Но современный компьютер выполнит любое вычисление, если просто изменить программу. Конечно, нашему примитивному устройству из картонной карточки никакие вычисления не под силу, не так ли? А вот и нет! Оно с ними справится! Студия Pixar даже смогла бы сделать с его помощью все необходимые вычисления для «Истории игрушек»! Конечно, пользоваться нашим устройством они бы не стали — это настолько утомительно и медленно, что заняло бы все время существования Вселенной, но скорость — это отдельный вопрос, который мы рассмотрим в следующей главе. Отметим, что наше устройство — это не обычная машина Тьюринга. Машина из картонной карточки — это универсальная машина Тьюринга.
Согласно великой идее Тьюринга, машина Тьюринга не просто выполняет систематический процесс — в ней воплощено то, что мы подразумеваем под «систематическим процессом» или «механистическим процессом». Даже сама по себе идея неплоха. К примеру, таким процессом — как сложить два числа, чтобы получить их сумму, — является алгоритм суммирования. Итак, должна существовать машина Тьюринга, которая «считывает» два числа со своей ленты, складывает их вместе и фиксирует сумму на ленте. И больше ничего не делает.
Другой систематический процесс — переворачивание буквенной строки. Например, если задана строка abcdefg, машина сначала меняет местами крайнюю пару букв, затем следующую и так далее. Процесс продолжается до тех пор, пока не закончатся пары для обмена или не останется только одна буква. В итоге у нас получится gfedcba. Следовательно, существует машина Тьюринга, которая выполняет эту операцию для любой произвольной строки на своей ленте, и ничего больше.
Однако суть идеи Тьюринга заключалась в доказательстве, что одна машина Тьюринга может делать все то же самое, что и любая другая машина Тьюринга. Одна машина способна выполнять все систематические процессы, включая сложение двух чисел или изменение буквенной строки. Это машина, умеющая «вычислять» все, что computable, все, что поддается вычислению, с использованием механистического процесса. В этом и заключается универсальность машинного вычисления. Когда мы говорим, что великой идеей Тьюринга была вычислительная машина, мы имеем в виду универсальную вычислительную машину. Современный компьютер — потомок именно этого типа, универсальной машины Тьюринга. Но как машина Тьюринга может быть универсальной?