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

правила в одной строке, если использовать односимвольные сокращения 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 на втором шаге выглядит так:

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

Затем она сымитирует следующий шаг, затем еще один и так далее. Фактическое создание такой конструкции — трудоемкий процесс, но суть его проста. Если вы готовы лишиться девственности (по Хайнлайну), читайте комментарии на сайте, где подробно описан процесс моделирования.

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

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

Универсальная машина Тьюринга — это, по сути, то, что мы теперь называем компьютером с хранимой в памяти программой, поскольку она хранит и программу, и данные одинаковым образом — и то и другое находится в однородном пространстве ее памяти. А компьютер с хранимой в памяти программой — это то, что мы называем просто «компьютер». Каждую конкретную машину А, представленную закодированными правилами, мы называем компьютерной программой или просто программой. Теперь вы понимаете, почему программисты часто называют себя кодерами. Они кодируют произвольный алгоритм, реализованный конкретной машиной Тьюринга, в одномерную форму, необходимую компьютеру U. На рисунке 3.5 показано, как универсальная машина Тьюринга U метафорически соответствует современному компьютеру.

Перечислим еще раз, чего добился Тьюринг. Он показал, что может существовать одна-единственная конструкция машины, способная делать все, что представлено систематическими инструкциями. Она не может забивать гвозди или нажимать на клавиши рояля, но она с легкостью исполнит какие-то систематические операции над символами (а вот с помощью полученных результатов — тоже символов — уже можно управлять машиной, которая забивает гвозди или нажимает на клавиши). Чтобы изменить то, что делает машина, нужно лишь изменить ее программу. Тьюринг изобрел концепцию компьютера, под которым мы ныне подразумеваем компьютер с хранимой в памяти программой. Мы реализуем его в виде электронного устройства, чтобы оно работало быстрее.

Рис. 3.5 Программа современного компьютера почти всегда разделена как минимум на две части. Одна из них называется операционной системой или ОС, например Windows, MacOS или Android. Она работает всегда. В этом случае желателен бесконечный цикл. Другая часть программы, которая изменяется в соответствии с вашими индивидуальными потребностями, называется приложением. Похожим образом в памяти хранятся данные, важные для операционной системы, отдельно от данных для приложения. Операционная система просто «занимается всякими делами», например загружает приложение в память в нужном