Пиксель. История одной точки - Элви Рэй Смит

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

Есть четыре возможных положения, которые принимает карточка, и есть шесть символов (считая пробел). Соответственно, существует шесть правил для каждого положения карты, по одному для каждого символа, который может появиться в окошке. Общее правило действий заключается в том, что на каждом шаге символ в окошке может измениться, сама карта — переместиться влево или вправо на одну клетку и принять другое положение. А еще дальнейшие действия могут просто прекратиться. Вот и все.

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

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

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

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

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

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

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

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

Буква A на рисунке 3.4 — любая простая машина Тьюринга, которая условно изображена как сканирующая головка, перемещающаяся влево и вправо по бесконечной ленте. В нашем примере это картонная карточка, а «сканирующая головка» — это отверстие в ней. Карточка будет нашим текущим примером произвольной машины Тьюринга A. Обозначим буквой U универсальную машину Тьюринга, которая может имитировать любую машину Тьюринга A при наличии одномерного описания правил работы A — набора команд — и описания данных на ленте A.

В нашем примере набор команд А — это всего 24 правила, которые определяют машину, сделанную из картонной карточки. Они перекодированы в форму, которую требуют правила машины U. Правила для машины A, записанные на картонной карточке, представлены в виде двух таблиц инструкций. Они написаны с двух сторон карточки, причем половина из них перевернута. Для U нужна одномерная версия этих правил на ленте, записанной набором символов, которые использует U. Вскоре мы покажем пример кодирования правил A.

Тьюринг заметил, что набор правил любой машины Тьюринга можно записать как одномерный ряд символов. В примере с карточкой можно перечислить все 24 ее