Никогда не пытайтесь объяснить устройство компьютера невеждам. Легче девственнице объяснить, что такое секс.
Иди к черту, Хайнлайн! Фокус Тьюринга, позволяющий сделать одну из его машин универсальной, гениален. Машина Тьюринга — это простая вещь, которая определяется набором правил. У нашей машины из картонной карточки, например, есть 24 правила, по 6 для каждого положения. Поэтому Тьюринг предположил, что существует возможность спроектировать машину Тьюринга, которая возьмет описание любой машины Тьюринга, а также входные данные для нее и смоделирует все то, что эта машина будет делать лентой. Он считал это возможным, потому что такое моделирование представляет собой систематический процесс, а машина Тьюринга изобретена для демонстрации исполнения именно того, что мы подразумеваем под систематическим процессом. Машина Тьюринга, которая имитирует любую другую, — это универсальная машина Тьюринга, и Тьюринг показал, как ее сконструировать.
Буква 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 получила свои входные данные.