(OCR) – один из относительно недавних триумфов компьютерного программирования – могут сканировать печатные страницы и достаточно точно преобразовывать их в текстовый файл (в котором каждый буквенный или численный символ представлен числом в кодировке ASCII, так что по тексту можно осуществлять поиск, а также подвергать его другим чудесам текстовой обработки, не используя ничего, кроме арифметики.) Может ли программа OCR читать? Не то чтобы. Она не понимает, что видит. Она вроде как читает, и это удивительно полезная способность, которую можно добавить в нашу богатую коллекцию структурных элементов.
секрет 4. Поскольку число может означать что угодно, оно может означать инструкцию или адрес.
Числом в регистре можно обозначать инструкцию, например 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 и т. д.) и перемещении лишь на одну ячейку зараз – гораздо более трудоемкий процесс, чем наши упражнения с регистровой машиной, но смысл при этом одинаков. Универсальная машина Тьюринга – это устройство с программой А (если хотите, встроенной), которая позволяет ему “считывать” программу Б с бумажной ленты и затем выполнять ее, используя остальную информацию с ленты в качестве вводных данных для программы Б. Регистровая машина Хао Вана способна выполнить любую программу, которую можно свести к арифметике и условным переходам, и таковы же возможности машины Тьюринга. Обе машины обладают чудесной способностью брать номер любой другой программы и выполнять этот номер. Вместо того чтобы конструировать сотни разных вычислительных машин, каждая из которых будет прошита для выполнения конкретной сложной задачи, достаточно создать единственную многоцелевую универсальную машину (с предустановленной программой А) и заставить ее исполнять наши запросы, пополняя ее программами – программным обеспечением, – создающими виртуальные машины.
Иными словами, универсальная машина Тьюринга представляет собой универсальный имитатор. То же самое можно сказать и о менее известной универсальной регистровой машине. И о вашем ноутбуке. Ваш ноутбук не делает ничего такого, что не могла бы сделать универсальная регистровая машина, и наоборот. Но не обольщайтесь. Никто не говорит, что все машины работают с одинаковой скоростью. Мы увидели, как ужасно медленно наша регистровая машина выполняет такую кропотливую операцию, как деление, которое она – мама дорогая! – осуществляет путем последовательного вычитания. Неужели нет способа ускорить процесс? Конечно есть. Фактически история компьютеров со времен Тьюринга до сегодняшнего дня – это как раз история поиска все более быстрых способов делать то, что делает регистровая машина, и ничего более.
секрет 6. Все усовершенствования компьютеров с момента изобретения воображаемой машины Тьюринга, движущейся по бумажной ленте, просто ускоряют их работу.
К примеру, Джон фон Нейман создал архитектуру для первого серьезного работающего компьютера, и чтобы ускорить его работу, он расширил окно головки записи-чтения машины Тьюринга, чтобы она читала зараз не один бит, а много. Многие ранние компьютеры читают 8-битные, 12-битные и даже 16-битные “слова”. Сегодня часто используются 32-битные слова. Это все еще узкое место – узкое место фон Неймана, – но оно в 32 раза шире узкого места машины Тьюринга! Прибегнув к некоторому упрощению, можно сказать, что слова по очереди копируются – COPY – из памяти в особый регистр (регистр инструкции), где эта инструкция читается – READ – и исполняется. Как правило, слово состоит из двух частей, кода операции (например, ADD, MULTIPLY, MOVE, COMPARE, JUMP-IF-ZERO) и адреса, который говорит компьютеру, к какому регистру обращаться за содержимым для проведения операции. Таким образом, 10101110 11101010101 может говорить компьютеру выполнять операцию 10101110 на содержимом регистра 11101010101, всегда помещая ответ в специальный регистр, называемый аккумулятором. Существенное различие между регистровой машиной и машиной фон Неймана заключается в том, что регистровая машина может осуществлять операции на любом регистре (само собой, только операции Инк и Деп), а машина фон Неймана выполняет всю арифметическую работу в аккумуляторе и просто копирует и перемещает – COPY и MOVE – содержимое в регистры памяти (или накапливает его – STORE – в этих регистрах). Все эти дополнительные перемещения и копирования окупаются возможностью осуществлять большое количество аппаратно-реализованных базовых операций. Иначе говоря, существует одна электронная схема для операции ADD, другая – для операции SUBTRACT, третья – для операции JUMP-IF-ZERO и так далее. Код операции напоминает код города в телефонной системе или индекс в почтовом адресе: он отправляет то, над чем работает, в верное место для исполнения. Так программное обеспечение встречается с аппаратным.
Сколько примитивных операций содержится сегодня в настоящих компьютерах? Сотни и даже тысячи. Кроме того, как в старые добрые времена, компьютер может быть наделен сокращенным набором команд (работать на архитектуре RISC): такой компьютер умеет выполнять лишь несколько десятков примитивных операций, но при этом работает молниеносно. (Если инструкции Инк и Деп можно исполнять в миллион раз быстрее, чем аппаратно-реализованную операцию ADD, будет целесообразно составить программу ADD, используя Инк и Деп, как мы делали ранее, и для всех операций сложения, предполагающих менее миллиона шагов, мы останемся в выигрыше.)
Сколько регистров содержится сегодня в настоящих компьютерах? Миллионы и даже миллиарды (но все они конечны, так что огромные числа должны распределяться по большому числу регистров). Байт состоит из 8 бит. Имея на своем компьютере 64 мегабайта RAM (оперативной памяти), вы имеете шестнадцать миллионов 32-битных регистров – или их эквивалент. Мы знаем, что содержимое регистров может обозначать не только положительные целые числа. Действительные числа (например, π, √2 или ⅓) хранятся в форме чисел “с плавающей запятой”. Эта форма представления разбивает число на две части, мантиссу и порядок, как в экспоненциальной записи (“1,495 × 1041”), что позволяет компьютеру производить арифметические действия, чтобы работать с числами (в приближенном представлении), которые натуральными не являются. Операции с плавающей запятой – это обычные арифметические операции (в частности, умножение и деление) над числами с плавающей запятой, и самый быстрый суперкомпьютер, который можно было купить двадцать лет назад (когда я написал первую версию этой главы), имел производительность более 4 мегафлопс (от англ.