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

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

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

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

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

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

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

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

Сколько программ может выполнить компьютер? Сколько приложений он может запускать? Их настолько много, что вы их даже не сосчитаете. Это все равно что спросить, сколько музыкальных произведений может сыграть рояль. Компьютер — самый гибкий инструмент, когда-либо созданный человечеством. Это чудо Гибкости. Цифровой Свет — лишь один из миров, записанный на его бесконечной ленте.

Джонни фон Нейман

Принститут — сленговое название Института перспективных исследований в городе Принстон — притягивал гениев, особенно тех, кто бежал из нацистской Европы. Когда Тьюринг и Ньюман приехали туда в конце 1930-х (первый — для учебы в аспирантуре, второй — в творческий отпуск), там уже сияло небольшое, но впечатляющее созвездие ученых. Например, в Принституте тогда работал Альберт Эйнштейн. Но для нашей истории важнее, что там оказался Джон фон Нейман.

Янош Лайош Нейман родился 28 декабря 1903 года в Будапеште. Его отец, банкир Макс Нейман, в 1913 году получил от правительства Австро-Венгрии дворянский титул (предположительно, за финансовую помощь), что позволило ему добавить приставку «фон» к австрийской фамилии. Так что его сын стал известен в Америке как Джон фон Нейман. Он переехал туда навсегда в 1933 году и стал одним из первых преподавателей Принститута.