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

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

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

Тьюринг заметил, что набор правил любой машины Тьюринга можно записать как одномерный ряд символов. В примере с карточкой можно перечислить все 24 ее правила в одной строке, если использовать односимвольные сокращения f(ront), b(ack), F и B для четырех положений карточки — лицевой, обратной, повернутой лицевой и повернутой обратной — и разделить правила на четыре группы, по шесть правил в каждой:

(шесть правил f) (шесть правил b) (шесть правил F) (шесть правил B)

Как может выглядеть эта перекодировка на самом деле, можно посмотреть в комментариях на сайте.

Первый фокус, проделанный Тьюрингом, — это запись линейного описания машины А на ленте U, по одному символу на каждую ячейку ленты. Представьте, что это записано на левой половине ленты.

Второй фокус Тьюринга — сделать линейное описание ленты А, содержащее все ее исходные данные, справа от описания машины А. Кодировка здесь предельно проста, данные просто переносятся ячейка в ячейку. Таким образом, описание и исходные данные нашей машины-карточки могут выглядеть следующим образом, если мы используем вертикальную черту для разделения двух наборов и 0 для кодирования пробела:

Рис. 3.4. Под данными для А мы подразумеваем некие символы, изначально записанные на ее ленте — например, для карточки из нашего примера исходными данными была запись 5155. Их также надо перекодировать в форму, требуемую для U. Ниже мы также приведем пример такого перекодирования. Иначе говоря, исходные данные на ленте универсальной машины Тьюринга U состоят как из правил A, так и из данных A в одномерной форме, как показано на рисунке.

(шесть правил f) (шесть правил b) (шесть правил F) (шесть правил B) | 000000051550000000

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

Универсальной машине теперь нужно «узнать» еще только две вещи, чтобы сымитировать произвольную машину А: какой символ машина А сканирует в данный момент и в каком положении она находится в данный момент. Третий фокус Тьюринга — это добавление в левой части ленты символа, указывающего текущее состояние, и еще одного символа в правой половине, указывающего, какая ячейка просматривается в данный момент. Четыре компонента информации о произвольной машине А — ее описание, начальные данные, начальное положение и отсканированный в начальной позиции символ — образуют начальные данные для универсальной машины. Вот представление входной ленты U для машины-карточки в перевернутом положении, с исходными данными 5155, первоначально стоящей в позиции сканирования пустой ячейки (0) справа, как на рисунке 3.3:

(шесть правил f) (шесть правил b) (шесть правил F) (шесть правил B) | 000000051550000000

Жирным 0 отмечен сканируемый в начальной позиции символ, а жирным b отмечено начальное положение карточки, то есть указано, какой набор правил использовать. Посмотрите в комментариях на сайте, как на самом деле может выглядеть лента для U.

Разработка такого набора правил для U, чтобы она могла имитировать произвольную машину A, закодированную описанным выше способом на ленте машины U, — долгий и муторный процесс. Суть в том, что U может «видеть» полное описание произвольной машины и полное описание данных для нее. Она может видеть текущее положение произвольной машины и считываемую ею в данный момент ячейку ленты данных. Это полное описание моделируемой машины — на данный момент. Аналогичным образом моделируется следующее положение произвольной машины, и Тьюринг в своей знаменитой статье 1936 года описал U, которая систематически преобразовывала отображение для одного момента в отображение для следующего момента. Таким образом, в процессе моделирования машины-карточки лента U на втором шаге выглядит так: