Насосы интуиции и другие инструменты мышления

Числом в регистре можно обозначать инструкцию, например ADD, SUBTRACT, MOVE или SEARCH, и адреса (регистров в компьютере), поэтому мы можем хранить всю последовательность инструкций в ряде регистров. Если наша основная программа (программа А) велит машине переходить от регистра к регистру, выполняя содержащиеся в регистре инструкции, тогда в эти регистры можно поместить и вторую программу, программу Б. Когда машина начинает выполнение программы А, первым делом она обращается к регистрам, которые велят ей выполнять программу Б, что машина и делает. Это означает, что можно раз и навсегда поместить программу А в центральный блок обработки данных регистровой машины, зарезервировав для нее ряд регистров (она может стать “встроенной программой”, вшитой в ПЗУ – постоянное запоминающее устройство), а затем использовать программу А, чтобы запускать программы Б, В, Г и так далее, в зависимости от того, какие числа мы помещаем в обычные регистры. Устанавливая программу А на нашу регистровую машину, мы превращаем эту машину в компьютер с хранимой в памяти программой.

Программа А наделяет регистровую машину способностью добросовестно выполнять любые инструкции, которые мы помещаем (по номерам) в регистры. Любая подлежащая выполнению программа состоит из упорядоченной последовательности чисел, к которым по порядку обращается программа А, исполняющая инструкции, обозначенные этими числами. Если разработать систему, которая будет унифицировать эти инструкции (к примеру, присваивать им имена одинаковой длины – скажем, двузначные), можно будет считать всю серию чисел, составляющих программу Б, скажем

86, 92, 84, 29, 08, 50, 28, 54, 90, 28, 54, 90

одним большим и длинным числом:

869284290850285490285490

Это число одновременно представляет собой уникальное “имя” программы, программы Б, и саму программу, которая пошагово выполняется программой А. Вот другая программа:

28457029759028752907548927490275424850928428540423

и третья:

8908296472490284952498856743390438503882459802854544254789653985,

но самые интересные программы имеют гораздо более длинные имена, включающие миллионы знаков. Программы, хранимые в памяти вашего ноутбука, например текстовый процессор и браузер, представляют собой именно такие длинные числа, состоящие из многих миллионов (двоичных) знаков. Программа размером 10 мегабит – это последовательность из восьмидесяти миллионов нулей и единиц.

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

Блестящий теоретик и философ Алан Тьюринг вывел эту схему, используя другой простой воображаемый компьютер, который движется по разделенной на ячейки бумажной ленте. Поведение этого компьютера зависит (ага! – условный переход) от того, считывает он ноль или единицу из той ячейки, которую обрабатывает в данный момент. Машина Тьюринга умеет только менять бит (стирать 0, записывать 1 – и наоборот) или оставлять бит нетронутым, а затем перемещаться влево или вправо на одну ячейку и переходить к следующей инструкции. Думаю, вы согласитесь, что создание программ сложения, вычитания и других функций для машины Тьюринга при использовании только двоичных чисел 0 и 1 вместо всех натуральных чисел (0, 1, 2, 3, 4, 5 и т. д.) и перемещении лишь на одну ячейку зараз – гораздо более трудоемкий процесс, чем наши упражнения с регистровой машиной, но смысл при этом одинаков. Универсальная машина Тьюринга – это устройство с программой А (если хотите, встроенной), которая позволяет ему “считывать” программу Б с бумажной ленты и затем выполнять ее, используя остальную информацию с ленты в качестве вводных данных для программы Б. Регистровая машина Хао Вана способна выполнить любую программу, которую можно свести к арифметике и условным переходам, и таковы же возможности машины Тьюринга. Обе машины обладают чудесной способностью брать номер любой другой программы и выполнять этот номер. Вместо того чтобы конструировать сотни разных вычислительных машин, каждая из которых будет прошита для выполнения конкретной сложной задачи, достаточно создать единственную многоцелевую универсальную машину (с предустановленной программой А) и заставить ее исполнять наши запросы, пополняя ее программами – программным обеспечением, – создающими виртуальные машины.