Вторая важная идея, на которую опирается наш информационный век, — универсальность машинных вычислений. В 1936 году Алан Тьюринг описал «машину Тьюринга» — абстрактную вычислительную машину, которая состоит из бесконечно длинной ленты, разделенной на клетки с цифрами 1 или 0. Машина считывает одну клетку за другой и содержит набор правил в виде пронумерованных состояний, фактически представляющих собой хранимую в памяти программу. Каждое правило предписывает машине совершить одно действие, если в считываемой клетке стоит 0, и другое действие, если в считываемой клетке стоит 1. Возможные действия включают запись 0 или 1, перемещение ленты на одну клетку вправо или влево, остановку ленты. Каждое состояние содержит номер следующего состояния, в которое должна перейти машина. Завершив алгоритм, машина останавливается; выход процесса остается на ленте. Хотя лента теоретически бесконечна, любая программа (которая не подразумевает бесконечный цикл) использует конечную часть ленты; следовательно, если мы ограничимся конечной памятью, машина по-прежнему сможет решать широкий круг задач.
В машине Тьюринга нет ничего сложного, верно? На самом деле именно этого и добивался ученый. Он хотел, чтобы его машина была максимально простой (но не проще, перефразируя Эйнштейна). Позже Тьюринг и его бывший учитель, Алонзо Черч сформулировали тезис Черча — Тьюринга, согласно которому задача, которая не может быть решена машиной Тьюринга, не может быть решена никакой другой машиной. Хотя собственно машина Тьюринга способна выполнять крайне ограниченное количество команд и одновременно обрабатывает всего один бит, она может вычислить все, что может вычислить любая вычислительная машина.
Строгие интерпретации тезиса Черча — Тьюринга предполагают принципиальную эквивалентность того, что человек может думать или знать, и того, что может быть вычислено машиной. Основная идея заключается в том, что человеческий мозг подчиняется естественным законам; следовательно, его способность обрабатывать информацию не может превосходить таковую у машины (и соответственно у машины Тьюринга).
В своей статье Тьюринг заложил теоретические основы машинных вычислений. Хотя это целиком и полностью его заслуга, важно отметить, что большое влияние на него оказала лекция, прочитанная Джоном фон Нейманом в 1935 году в Кембридже (Англия). Лекция была посвящена идее программы, которую можно хранить в памяти — концепция, позднее воплощенная в машине Тьюринга. На фон Неймана в свою очередь произвела глубочайшее впечатление статья Тьюринга 1936 года, где были изложены принципы машинных вычислений и которую в конце 1930-х — начале 1940-х годов он включил в список обязательной литературы, составленный для своих коллег.
В той же работе Тьюринг сообщает о другом неожиданном открытии, а именно — о проблеме неразрешимых задач. Неразрешимые задачи — это хорошо описанные задачи с однозначным ответом, который, однако, не может быть вычислен на машине Тьюринга (т. е. на любой машине). Это противоречит постулату XIX века, гласящему, что все задачи, которые могут быть описаны, в конечном счете будут решены. Тьюринг показал, что неразрешимых задач столько же, сколько и разрешимых. В своей «Теореме о неполноте» 1931 года Курт Гедель приходит к аналогичному выводу. Таким образом мы оказываемся в странной ситуации: с одной стороны, мы можем описать задачу и доказать, что однозначный ответ существует, а с другой — знаем, что ответ никогда не будет найден.
Гораздо больше можно сказать о философском значении работ Тьюринга, Черча и Геделя, однако в рамках данного предисловия достаточно отметить следующее. Тьюринг показал, что в основе всех машинных вычислений лежит очень простой механизм. Поскольку машина Тьюринга (и, следовательно, любая вычислительная машина) способна определять дальнейший образ действий, исходя из результатов предыдущих операций, она способна принимать решения и моделировать произвольно сложные иерархии данных.
К декабрю 1943 года Тьюринг спроектировал и построил «Колосс», который часто называют первым компьютером в истории электронных вычислительных машин. «Колосс» предназначался для выполнения одной-единственной задачи — декодирования радиосообщений, зашифрованных нацистской машиной Enigma — и не мог быть перепрограммирован для выполнения другой задачи. Зато с дешифровкой он справлялся блестяще: считается, что именно благодаря ему союзники смогли взять верх над немецкими «люфтваффе» и выиграть решающую битву за Британию.
Все вышеизложенное послужило своеобразным фундаментом, на котором Джон фон Нейман создал архитектуру современного компьютера — машину фон Неймана, составляющую основу практически каждого автомата, изобретенного за последние шестьдесят шесть лет: от микроконтроллера стиральных машин до самых больших суперкомпьютеров. Это третья ключевая идея информационной эры. В статье «Первый проект отчета о EDVAC», [EDVAC (Electronic Discrete Variable Automatic Computer) — одна из первых электронных вычислительных машин на двоичной основе. — Здесь и далее примеч. ред.] датированной 30 июня 1945 года, фон Нейман изложил революционные принципы в области машинных вычислений. Модель фон Неймана состоит из центрального процессора, в котором выполняются арифметические и логические операции, блока памяти, в котором хранятся программа и данные, устройства массовой памяти, счетчика команд и каналов ввода-вывода. Данная концепция описана в первой части этой книги. Хотя статья фон Неймана, по сути, представляла собой внутренний проектный документ, она не только стала библией для конструкторов вычислительных машин 1940-х и 1950-х годов, но и значимо повлияла на архитектуру всех компьютеров, построенных с тех пор.
Машина Тьюринга не была рассчитана на практическое применение. Теоремы Тьюринга не имели никакого отношения к эффективности решения задач; они лишь позволяли определить круг тех задач, которые могли быть решены посредством машинных вычислений. Фон Нейман, наоборот, ставил своей целью формулирование практических принципов вычислительной машины. Так, в машине фон Неймана однобитовые вычисления Тьюринга заменены многобитовыми словами (как правило, количество битов кратно восьми). Если машина Тьюринга тратит огромное количество времени на перемещение ленты вперед и назад, чтобы сохранять и извлекать промежуточные результаты, то машина фон Неймана, напротив, снабжена памятью с произвольным доступом, поэтому любой элемент данных может быть извлечен немедленно.
Одним из важнейших принципов, предложенных фон Нейманом, является принцип хранимой программы, который он сформулировал десятью годами ранее: программа хранится в той же памяти, что и данные. Это позволяет перепрограммировать вычислительную машину для выполнения различного рода задач, а также использовать самомодифицирующийся код, допускающий применение некоторых форм рекурсии. До того времени практически все вычислительные машины, включая «Колосс» Тьюринга, могли решать только те задачи, для решения которых были предназначены изначально. Хранимая программа придала вычислительной машине поистине универсальный характер. Так, идея Тьюринга об универсальной машине получила реальное воплощение.
Другой ключевой принцип фон Неймана заключается в том, что каждая инструкция должна содержать код арифметической или логической операции, которую необходимо выполнить, а также адрес операнда в памяти. Данная формула впервые была предложена фон Нейманом в рамках его публикации, посвященной совместному с Дж. Преспером Эккертом и Джоном Мокли проекту EDVAC. Сам EDVAC был запущен только в 1951 году; к тому времени уже существовали другие вычислительные машины с хранимыми программами, в частности Манчестерская малая экспериментальная машина, ENIAC, [ENIAC (русск. ЭНИАК) — электронный числовой интегратор и вычислитель, сокр. от Electronic Numerical Integrator and Computer, первый электронный цифровой вычислитель общего назначения, который можно было перепрограммировать для решения широкого спектра задач. // О нем была короткая публикация в узкоспециальном журнале «Законность» (Стуканов А. Дело ленинградских литераторов // Законность. 2004. № 8. С. 51–52), однако в ней оказалось много небрежностей и путаницы (в частности, само дело, следствие по которому длилось с февраля по июнь 1932 года, приписано к декабрю 1934-го). ] EDVAC [EDVAC (русск. ЭДВАК) — сокр. от Electronic Discrete Variable Automatic Computer, одна из первых электронных вычислительных машин. В отличие от своего предшественника ЭНИАКа, это был компьютер на двоичной, а не десятичной основе.] и BINAC. [BINAC (русск. БИНАК) — сокр. от англ. Binary Automatic Computer, двоичный автоматический компьютер, электронный компьютер первого поколения, построенный в США компанией Eckert-Mauchly Computer Corporation и запущенный в апреле или августе 1949 года. Формально считается первым коммерческим электронным компьютером.] Все они были созданы под влиянием работ фон Неймана теми же конструкторами: Эккертом и Мокли. Фон Нейман принял непосредственное участие в проектировании ряда этих машин, включая более позднюю версию ENIAC, которая поддерживала хранимую программу.
Можно назвать несколько предшественников архитектуры фон Неймана, однако ни один из них не являлся истинной машиной фон Неймана, за одним неожиданным исключением. «Марк I» Говарда Эйкена, построенный в 1944 году, имел элемент программируемости, но не использовал хранимую программу. Эта вычислительная машина считывала инструкции с перфорированной бумажной ленты, а затем выполняла каждую команду отдельно. Поскольку ветвления в программе отсутствовали, ее нельзя рассматривать как пример архитектуры фон Неймана.
Еще до «Марка I», в 1941 году, Конрадом Цузе была создана вычислительная машина Z3. Она тоже считывала программу с ленты (точнее, с перфорированной кинопленки) и не могла совершать условные переходы. Интересно, что Цузе получил поддержку от немецкого Научно-исследовательского института авиации, который использовал Z3 для своих расчетов, однако его просьба о государственном финансировании замены реле на электронные трубки была отклонена. Нацисты считали, что машинные вычисления «не помогут выиграть войну».
Единственный истинный предшественник концепции фон Неймана появился на целых 100 лет раньше. В аналитической машине Чарльза Бэббиджа, описанной им впервые в 1837 году, идея хранимой программы реализована с помощью перфорированных карт, заимствованных из ткацкого станка Жаккара. Память с произвольным доступом была рассчитана на одну тысячу слов по 50 десятичных цифр каждое (около 21 килобайта). Инструкции не только содержали код операции и номер операнда, как и все современные языки программирования, но и включали ветвление и циклы. Это значит, что описанное Бэббиджем представляло собой настоящую машину фон Неймана. Впрочем, он явно не мог вообразить себе всех технических и организационных сложностей, связанных с проектированием такого рода автоматов, а потому его аналитическая машина так и осталась недостроенной. Неясно, знали ли пионеры информатики ХХ века, в том числе фон Нейман, о наработках Бэббиджа.
