Фон Нейман Дж. Теория самовоспроизводящихся автоматов:
Пер. с англ.

Оглавление

От редактора перевода

В сентябре 1962 г. на Международном симпозиуме по теории релейных устройств и конечных автоматов канадский профессор Г.Глинский сказал по поводу статьи Дж. фон Неймана "Вероятностная логика и синтез надежных организмов из ненадежных компонент":

"Есть одна опасность в обращении с классическими работами. Кажется, что на них все ссылаются, но редко кто их действительно читает. Это приводит ко всевозможным недоразумениям. В случае статьи фон Неймана эти недоразумения еще более усугубляются его трудной манерой изложения".

Сказанное в полной мере можно отнести к предлагаемой вниманию советского читателя книге Дж. фон Неймана "Теория самовоспроизводящихся автоматов". В течение почти 10 лет многие авторы ссылались на результаты, полученные фон Нейманом в области моделей самовоспроизведения, зная об этом в лучшем случае по упоминанию об этих результатах в работах А.Бёркса и К.Шеннона.

А.Бёркс, редактор этой книги, не только подготовил к печати черновые записи Дж. фон Неймана, но и закончил его работу, завершив конструкцию самовоспроизводящегося автомата и придав книге законченный вид. В связи с этим мне хочется процитировать профессора Честера Ли: "Громадная работа по расшифровке рукописи и выяснению скрытых мотивов, которыми руководствовался один из наиболее блестящих и оригинальных умов, была предпринята профессором Бёрксом из Мичиганского университета. Он не только отредактировал рукопись, но и внес в нее много собственных идей и в то же время прояснил тот лабиринт отрывочных рассуждений, который характерен для рукописи Дж. фон Неймана. Все, кто работают в области клеточных автоматов, глубоко обязаны профессору Бёрксу за его неутомимые усилия в завершении рукописи и за его старания сделать труд Дж. фон Неймана по-настоящему понятным и доступным".

Артур Бёркс является одним из ведущих специалистов в области теории логических сетей и конечных автоматов. Опубликованная им совместно с Дж.Райтом в 1953 г. статья "Теория логических сетей" (переведена на русский язык в 1962 г., Кибернетический сборник, вып.4) явилась одной из первых работ, сформировавших современную теорию автоматов.

Научные интересы Бёркса очень широки – от формальной логики и теории автоматов до проектирования вычислительных машин, включая вопросы построения адаптивных систем, организацию взаимодействия вычислительных машин, моделирование естественных систем. С 1967 г. он возглавляет факультет вычислительной техники и теории связи Мичиганского университета.

В течение многих лет А.Бёркс был одним из ближайших сотрудников Дж. фон Неймана, поэтому трудно представить себе более подходящую кандидатуру для завершения работы, начатой Дж. фон Нейманом. Огромный труд, проделанный Бёрксом, позволяет считать его соавтором книги.

Специально для русского издания А.Бёркс написал предисловие и прислал ряд исправлений. Мы весьма признательны ему за эту любезность.

Содержания самой книги и идей, лежащих в основе ее построения, мы не касаемся, отсылая читателей к введению.

Предисловие к русскому изданию

В настоящей книге поставлен и решен отнюдь не очевидный вопрос о том, какого рода логическая организация достаточна для того, чтобы некоторый автомат был способен воспроизводить себя. Этот вопрос объединяет понятия из различных областей: биохимии, техники, логики. Он очень важен для нового (возникшего примерно в 1948 г.) направления – теории автоматов, или кибернетики. Главными создателями этого направления были Джон фон Нейман и Норберт Винер. Хотя они и находились под взаимным влиянием, но все же их подходы и интересы были различными. Фон Нейман назвал свой вариант "теорией автоматов", а Винер – "кибернетикой".

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

В планы фон Неймана входило создать систематическую теорию, математическую и логическую по форме, которая упорядочила бы понятия и принципы, касающиеся структуры и организации естественных и искусственных систем, роли языка и информации в таких системах, программирования и управления такими системами. Теория автоматов лежит на стыке разных дисциплин, объединяет различные подходы (с точки зрения логики, теории связи, физиологии), но в конце концов ей предстоит стать отдельной самостоятельной дисциплиной.

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

Винер подчеркивал роль понятия обратной связи, поскольку понимал его важность как для управления, так и для целенаправленного поведения. Фон Нейман сравнительно мало говорит об обратной связи, но фактически использует это понятие в большей части того, что им сделано. Все вычислительные машины, кроме разве самых примитивных, имеют обратную связь: она проявляется как наличие схемных циклов в неизменяемой части машины и как ветвления и условные инструкции в ее перестраиваемой части.

И кибернетику, и теорию автоматов вызвал к жизни технический прогресс, главным образом успехи, достигнутые в области электронных цифровых машин. Практические последствия этого американского изобретения хорошо известны, но о его влиянии на теорию говорилось мало. Я имел счастье лично участвовать в создании вычислительных машин как в практическом, так и теоретическом планах, благодаря чему мог наблюдать, как техника стимулировала развитие теории. Я был одним из главных конструкторов машины ENIAG – первой электронной вычислительной машины. Позже я сотрудничал с фон Нейманом и другими при разработке машины EDVAC, а потом работал с ним же над схемой вычислительной машины Института перспективных исследований.

Основываясь на этом своем опыте, я попытался во введении показать, как практическая работа фон Неймана с вычислительными машинами послужила основой для его теоретических исследований.

Что такое самовоспроизведение в какой-нибудь естественной системе, такой, как живая клетка, всем понятно. Этот вопрос в последнее время интенсивно изучали биологи, биохимики и генетики и получили замечательные, далеко идущие результаты. Разговор о самовоспроизведении искусственной системы, такой, как цифровая вычислительная машина, или даже о "логике" самовоспроизведения на первый взгляд кажется странным. В самом деле, между проблемой понимания самовоспроизведения естественной системы на генетическом и биохимическом уровнях и логической, автоматно-теоретической проблемой самовоспроизведения, сформулированной фон Нейманом, существует глубокое различие. Я сейчас постараюсь показать, что это различие не столь велико, как кажется. Для этого я сделаю краткий обзор основных результатов части I ("Теория и организация сложных автоматов") и части II ("Теория автоматов: конструирование, воспроизведение, однородность") настоящей книги.

Рассмотрим идеализированную синхронную цифровую вычислительную машину, сконструированную только из переключательных элементов (например, "и", "или" и "нет") и линий задержек (задерживающих импульсы на 1 единицу времени). Такая вычислительная машина представляет собой конечный автомат, имеющий конечное число частей и конечное число состояний. Входом пусть служит узел ленты, который, получая соответствующую команду от вычислительной машины, перемещает свою ленту на ячейку вперед и который может считывать для вычислительной машины содержимое просматриваемой ячейки. Аналогично выходом пусть будет другой узел ленты, способный производить записи в ячейку своей ленты и перемещать эту ленту вперед, получая соответствующий сигнал от вычислительной машины.

Таким образом, у нас получился конечный автомат с входным и выходным узлами ленты. Такой конечный автомат можно превратить в машину Тьюринга, присоединив к нему третий узел ленты, способный перемещать ленту в обоих направлениях, считывать с ленты и записывать на нее. На основе подходящего конечного автомата, от которого не требуется слишком большая сложность, мы получили универсальную вычислительную машину, способную осуществить любое вычисление, которое можно выполнить на какой-то вычислительной машине. Любая неспециализированная вычислительная машина, снабженная достаточным количеством ленты, представляет собой универсальную вычислительную машину.

Имея достаточные сведения о биохимии процесса самовоспроизведения клетки, можно было бы промоделировать его на универсальной вычислительной машине. Хотя наука близка к тому, чтобы осуществить реальное моделирование самовоспроизведения, она еще не вполне готова к этому и, безусловно, была далеко от этой цели в 1948 г. Так или иначе, фон Нейман всегда старался использовать идеи, возникшие в биологии, для обогащения теории автоматов.

В классе описанных выше идеализированных вычислительных машин центральная вычислительная машина, т.е. конечный автомат, синтезировалась из частей, чего нельзя сказать о входном и выходном узлах ленты, а также об узле ленты, предназначенном для запоминания. Более того, внешняя среда для этой машины никак не была представлена. Кинематическая модель самовоспроизведения, принадлежащая фон Нейману, должна была явиться элементом теории автоматов этого рода. Эта модель занимает центральное место в части I настоящей книги

Фон Нейман вначале рассматривал два типа основных элементов автомата, о которых мы уже говорили. Это переключательные элементы и линии задержки. Затем он ввел еще пять типов основных элементов: элемент, способный к восприятию (например, способный видеть или чувствовать); элемент, осуществляющий действие (например, искусственная рука); элемент, способный разделять другие элементы; элемент, способный соединять предметы; и, наконец, стержень, позволяющий построить жесткий каркас для ансамблей элементов.

В принципе из всех этих элементов можно построить автомат, способный не только вычислять, но и воспринимать, действовать, перемещать, отделять предметы друг от друга и конструировать другие автоматы. Внешнюю среду для этих идеализированных кинематических автоматов можно представлять себе в виде безбрежного океана, по поверхности которого плавает неограниченное число экземпляров основных элементов каждого типа. Это переключательные элементы, чувствительные органы, органы действия, разделяющие органы, объединяющие органы и стержни – все они совершают случайное движение, как молекулы газа. Таким образом, каждый автомат, помещенный на поверхность этого океана, снабжается частями в неограниченном количестве.

Весь процесс кинематического самовоспроизведения осуществляется следующим образом. Вообразите, что на поверхности нашего океана плавает кинематический автомат, представляющий собой конечный автомат М_u, соединенный с лентой Т. Основу этой ленты составляет зигзагообразная цепочка из стержней, причем в каждом пересечении можно поместить еще один стержень, символизирующий 1; отсутствие такого стержня будет символизировать 0 (см. рис.2). Конечный автомат М_u обладает возможностями конечной части универсальной вычислительной машины – он может управлять лентой Т и интерпретировать произвольную вычислительную программу, хранящуюся на этой ленте. Кроме того, автомат М_u имеет воспринимающие, действующие, объединяющие и разделяющие органы, соединенные между собой так, что он может подбирать стержни с поверхности океана и использовать их для изменения хранящейся на ленте информации и для неограниченного удлинения этой ленты. Поэтому комплекс, состоящий из автомата М_u и ленты Т, является универсальной вычислительной машиной.

В этом мире кинематических автоматов универсальная конструирующая машина обобщает универсальную вычислительную машину. Любая конечная машина М составлена из конечного числа основных элементов, соединенных определенным образом, и поэтому ее можно полностью охарактеризовать конечным описанием D (М), которое можно представить на ленте. Пусть М_с – конечная часть универсальной конструирующей машины. Конструктор М_с обладает возможностями трех типов. Во-первых, он может сделать все, что может сделать универсальная вычислительная машина М_u. Во-вторых, может сконструировать любую конечную машину М, если ему дано полное ее описание D (М). Чтобы выполнить такое конструирование, М_с прочитывает описание D (М), находит и собирает части, необходимые для М, и соединяет их между собой в соответствии с планом D (М). В-третьих, он может скопировать D (M) на новой ленте и присоединить эту ленту к М.

Пусть узел, который мы хотим сконструировать, состоит из произвольной машины М и присоединенной к ней ленты, содержащей D (М). Универсальный конструктор при условии, что на его ленте находится описание D (М), действует следующим образом. Сначала М_с считывает D (М), подбирает необходимые для М части и соединяет их между собой в соответствии с планом D (М). Затем М_с изготавливает копию ленты D (М). Таким образом, универсальный конструктор, отправляясь от описания D (М) и имея соответствующее снабжение частями, конструирует машину М с лентой D (М). Общая схема этого конструирования такова:

(1) М_с с лентой D (М) конструирует М с лентой D (М). Заметим, что конструируемая машина содержит свое собственное описание. Чтобы получить самовоспроизведение как частный случай этой общей схемы, заменим М в (1) на Мс и тогда получим:

(2) М_с с лентой D (М_с) конструирует М_с с лентой D (М_с).

При выполнении (2) универсальный конструктор М_с сначала считывает описание D (М_с), подбирает части, необходимые для М_с, и соединяет их в соответствии с планом D (М_с). Затем М_сизготавливает копию ленты D (М_с) и присоединяет ее к М_с. Универсальный конструктор делает все это, не зная, что изготавливается его копия и копируется его описание. Тем не менее весь процесс начинается с одного экземпляра М_с с лентой В (М_с), а оканчивается двумя экземплярами этого комплекса. Это и есть самовоспроизведение. (Подобные схемы обсуждаются в лекции 5 части I и в гл.5 части II и иллюстрируются на рис.50, 54, 55 и 56.)

"Блок-схемное" описание самовоспроизведения автоматов изложено здесь в общих чертах. Но даже при таком изложении видна аналогия между самовоспроизведением автоматов и процессом самовоспроизведения живой клетки. Лента Т с описанием D (М) аналогична несущим генетическую информацию цепям дезоксирибонуклеиновой кислоты (ДНК) в клеточном ядре. Операция копирования ленты D (М)M аналогична репликации ДНК, которая осуществляется под контролем фермента ДНК-полимеразы. Наконец, конструирование автомата М на основе информации D (М) аналогично конструированию новой клетки.

Специалисты по молекулярной биологии в настоящее время пытаются проследить логику этого процесса конструирования. Этот процесс осуществляется при участии системы из информационной рибонуклеиновой кислоты, транспортной рибонуклеиновой кислоты, ферментов и рибосом. Эта система производит сборку аминокислот согласно коду ДНК, в результате чего образуются белки (в том числе ферменты), которые направляют конструирование новой клетки.

Мы очертили пока лишь общую схему для самовоспроизведения автомата. Следующая задача фон Неймана состояла в том, чтобы довести эту общую схему до детальной логической конструкции. Чтобы сделать это, надо полностью описать возможности каждого элемента и правила работы этих элементов при взаимодействии друг с другом внутри машины и при взаимодействии машины с окружающей средой.

Рассмотрим в качестве примера конструирующий автомат. Он использует кинематические, разделяющие и объединяющие элементы для перемещения и работы с другими элементами. Каким образом конструирующий автомат находит эти элементы и обнаруживает те кинематические, разделяющие и объединяющие элементы, с которыми предстоит работать? Он мог бы сделать это с помощью самих кинематических, разделяющих и объединяющих элементов, если бы они сами обладали способностью к восприятию. Или он мог бы это сделать с помощью воспринимающих элементов, если бы смог координировать работу воспринимающего и кинематического (разделяющего или объединяющего) элементов.

Дать полный и точный список правил для кинематической системы, которые были бы в то же время простыми и прозрачными, довольно трудно. Кроме того, вряд ли кинематические, или двигательные, возможности этой системы дадут сами по себе что-нибудь ценное. С одной стороны, эти кинематические черты модели слишком далеки от химии, физики и механики, чтобы представить большой интерес сами по себе, а с другой стороны, они слишком далеки от проблем организации, управления и логики, чтобы продвинуть наше понимание этих проблем. Таким образом, двигательные возможности кинематической системы являются лишь источником сложностей, которые в настоящем контексте не оправдывают затрат, и поэтому их лучше исключить.

Представление о клеточном автомате как раз устраняет эти сложности. Фон Нейман положил его в основу своей разработки логических деталей самовоспроизведения автоматов. Часть II настоящей книги посвящена этой проблеме. Клеточный автомат состоит из неограниченно итерированного, или мозаичного, массива конечных автоматов, каждый из которых взаимодействует со своими соседями. Он представляет собой, таким образом, основные рамки, или "пространство", в которых происходят события, связанные с функционированием автомата, и для которых мы можем сформулировать точные и простые правила, или законы. Я имел возможность обсуждать проблемы клеточных автоматов в Москве в 1962 г., будучи гостем Академии наук СССР. Моя статья "Клеточные автоматы" была опубликована в сборнике "Теория конечных и вероятностных автоматов" (под редакцией М. А. Гаврилова, изд-во "Наука", М., 1965).

Существует много различных типов клеточных автоматов. Можно по-разному задавать геометрию клеточного пространства, отношения соседства, типы автоматов, законы переходов для системы, начальное состояние системы. Фон Нейман рассматривает эти возможности в гл.1 части II и принимает решение использовать однородный двумерный массив ("шахматную доску"), в котором каждый конечный автомат имеет 29 состояний. В гл.2 он определяет правило переходов. В гл.3 и 4 осуществляет ряд главных этапов конструирования. Здесь оригинальная рукопись фон Неймана обрывается. В гл.5 я показываю, как завершить конструирование.

Основной результат работы состоит в том, что из нее следует, что на этой системе клеток с 29 состояниями можно смоделировать универсальные конструирующие машины, универсальные вычислительные машины и самовоспроизводящиеся машины.

В случае самовоспроизведения конечное число клеток с самого начала организуется так, чтобы составить универсальный конструирующий автомат М_c. Его описание D (М_с) представляется в конечном линейном массиве клеток, выполняющем роль ленты, а остальная часть клеточной системы (окружающая среда) остается в пассивном, неорганизованном состоянии. Когда машина М_с активизируется, она работает и как вычислительная машина, и как конструктор, посылая в клеточное пространство информацию, позволяющую организовать в другой конечной части пространства копию машины М_с и ленты D (M_с). Таким образом, исходная конечная организация этой системы воспроизводит себя.

Настоящая книга открывает новый раздел в теории автоматов – общее исследование клеточных автоматов. В книге в основном разбирается одна частная система клеточного автомата, введенная фон Нейманом для исследования некоторых организационных и программных аспектов самовоспроизведения. Однако понятие клеточного автомата очень широко, оно допускает ряд существенных отклонений от системы фон Неймана. Можно менять геометрию пространства и отношения соседства; можно вместо детерминированных правил переходов рассматривать недетерминированные и вероятностные правила, можно задать неоднородные отношения соседства и функции переходов. Таким образом, понятие клеточной системы автомата весьма плодотворно. Его существенными чертами являются квантованные время и пространство, конечное число возможных состояний для каждой точки пространства-времени и вычислимая локальная функция переходов (не обязательно детерминированная или однородная по всему пространству), управляющая работой системы во времени.

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

Работа фон Неймана вдохновила многих на изучение клеточных автоматов. В ближайшее время выйдет моя книга, в которую войдут некоторые опубликованные и неопубликованные результаты в этой области.

Предисловие

В конце сороковых годов Джон фон Нейман начал создавать теорию автоматов. Он хотел построить систематическую теорию, которая была бы логико-математической по форме и позволяла понять как естественные системы (естественные автоматы), так и аналоговые и цифровые вычислительные машины (искусственные автоматы). Для этого он написал пять работ:

1. "Общая и логическая теория автоматов". Доклад, прочитанный в сентябре 1948 г. в Калифорнийском технологическом институте на симпозиуме по механизмам мозга в поведении; опубликован в 1951 г. См. Нейман [4].

2. "Теория и организация сложных автоматов". Пять лекций, прочитанных в Иллинойсском университете в декабре 1949 г. Они составляют часть I настоящей книги.

3. "Вероятностная логика и синтез надежных организмов из ненадежных компонент". Лекции, прочитанные в Калифорнийском технологическом институте в январе 1952 г. См. Нейман 17].

4. "Теория автоматов: конструирование, воспроизведение, однородность". Фон Нейман начал эту рукопись осенью 1952 г. и работал над ней около года. Она составляет часть II настоящей книги.

5. "Вычислительная машина и мозг". Написана в течение 1955 и 1956 гг., опубликована в 1958 г. См. Нейман [2].

Вторая и четвертая из перечисленных работ так и остались в виде рукописей, нуждающихся в основательном редактировании. Эти работы составляют две части настоящей книги, которая, таким образом, завершает цикл работ фон Неймана по теории автоматов. При подготовке к такой редакционной работе я изучил все, что было сделано фон Нейманом по вычислительным машинам, включая теорию автоматов. Обзор его результатов содержится во введении к настоящей книге.

Для фон Неймана особый интерес представляли достаточно сложные автоматы, такие, как нервная система человека, и необычайно большие вычислительные машины, появление которых он предвидел. Он хотел создать теорию логической организации сложных систем вычислительных элементов и считал, что такая теория совершенно необходима для создания очень больших вычислительных машин. Фон Нейман сосредоточил основные свои усилия на двух проблемах теории автоматов, тесно связанных со сложностью: на проблемах надежности и самовоспроизведения. Надежность компонентов ограничивает сложность автомата, который мы можем построить, а свойство самовоспроизведения требует достаточно высокого уровня сложности автомата.

Проблему надежности фон Нейман детально обсуждает в третьей из перечисленных работ, а исследования по самовоспроизводящимся автоматам представлены главным образом в настоящей книге. Часть II, составляющая основной объем книги, содержит логический синтез самовоспроизводящегося клеточного автомата; более короткая часть I посвящена общим проблемам сложных автоматов, ее центральный пункт – кинематическая модель самовоспроизведения (лекция 5). Поэтому выбор заголовка "Теория самовоспроизводящихся автоматов" для книги в целом кажется правильным.

К сожалению, преждевременная кончина не позволила фон Нейману придать законченную форму этим исследованиям. Рукописи обеих частей книги остались недописанными: они представляют собой лишь первые, черновые наброски. Но это компенсируется тем, что они позволяют увидеть могучий ум фон Неймана в процессе работы.Поэтому я приложил все усилия к тому, чтобы сохранить первоначальный дух рукописи и в то же время сделать книгу достаточно легко читаемой. Чтобы стало ясно, что представляли собой "сырые" рукописи, я расскажу о них и отмечу редакторские изменения.

Фон Нейман договорился написать книгу по теории автоматов на основе пяти лекций, прочитанных им в Иллинойсском университете в декабре 1949 г. В помощь ему была сделана магнитофонная запись этих лекций. К сожалению, запись и ее машинописная копия оказались плохими – с пропущенными словами и фразами, с неразборчивыми местами. Сам фон Нейман никогда не редактировал эту машинописную копию, а вместо этого предполагал использовать для обещанной книги рукопись четвертой из перечисленных работ. Магнитофонная запись его лекций не сохранилась. Несмотря на все это, лекции в Иллинойсе заслуживают опубликования, и сохранившийся их вариант, по необходимости сильно отредактированный, составляет часть I настоящей книги. Фон Нейман заранее приготовил вил подробный конспект лекций, и они в основном соответствовали этому конспекту. Он был озаглавлен "Теория и организация сложных автоматов" и начинался следующими тремя тезисами:

Логическая организация и недостатки быстродействующих цифровых вычислительных машин.

Сравнение тех или иных сложных автоматов (как искусственных, так и естественных).

Вывод из сравнения нервных систем, встречающихся в природе.

Затем идут заголовки к каждой из лекций вместе с перечнями вопросов, которые предполагалось рассмотреть на лекции. Они без всякого изменения воспроизведены в настоящей книге перед началом каждой лекции, хотя содержание лекций не соответствует в точности этим перечням.

Состояние рукописи потребовало большой редакторской работы. Машинописная копия магнитофонной записи особенно бедна в наиболее формальных местах лекций, где фон Нейман пользовался доской. Для этих мест в особенности оказались полезными два комплекта записей, сделанных на лекциях. Там, где это было возможно, я сохранил фразеологию фон Неймана, но я часто оказывался перед необходимостью использовать собственный язык. В ряде случаев мне показалось лучше кратко суммировать то, что говорил фон Нейман, чем пытаться реконструировать текст. Некоторые идеи, высказанные фон Нейманом на лекциях в Иллинойсе, известны также по его опубликованным работам или просто хорошо известны. В таких случаях я часто кратко излагаю основную мысль, высказанную фон Нейманом, или даю ссылки на его опубликованные работы. Мои замечания взяты в скобки. Восстановленный вариант слов фон Неймана в скобки не заключался, однако следует иметь в виду, что большая часть текста без скобок подверглась основательному редактированию.

Рукопись "Теория автоматов: конструирование, воспроизведение, однородность" находилась в несравненно лучшем состоянии. Это был, по-видимому, первый вариант работы, если не считать сделанного ранее наброска (с рисунками) процедуры, посредством которой узел управления памятью (УУП) удлиняет и укорачивает соединительную петлю С₄ и временную петлю С₂ в соответствии с инструкцией, поступающей из конструирующего узла (КУ) (см. разд. 4.1 и 4.2). Несмотря на то что рукопись была лишь черновым вариантом работы, ее вполне можно было бы опубликовать без изменений, если бы не недостатки следующих трех типов.

1. В рукописи не хватало многих из тех простых деталей, которые облегчают чтение. Не было подписей под рисунками. При ссылке на формулы, разделы, рисунки давался просто номер и не указывалось, к чему он относится – к формуле, разделу или рисунку. Заголовки разделов были написаны на отдельном листе. Также на отдельном листе были краткие пояснения, касающиеся подстрочных примечаний, которые фон Нейман собирался дать. Части автомата в тексте обозначались просто какими-нибудь буквами: например, А и В вместо моих КУ и УУП. Я проработал рукопись несколько раз и каждый раз удивлялся тому, как при таком малом наборе мнемонических средств фон Нейман мог следить за тем, что он делал.

Я снабдил рисунки подписями и закончил подстрочные примечания. Замечания, которые фон Нейман поместил прямо на рисунках, я перенес в текст. Были произведены и другие изменения, но в тексте они никак не выделены.

Наконец, я вставил свои примечания, комментарии, пояснения и резюме и добавил заключительную главу (гл.5). Все такие добавления взяты в квадратные скобки. Квадратные скобки, которые употреблял фон Нейман, всюду заменены фигурными, за исключением символов [0] и [1]. Кроме того, я добавил табл.I и V, а также несколько рисунков. Рисунки 1–8, 16, 18, 19, 22, 24, 28–36, 38, 39 и 41 принадлежат фон Нейману, остальные сделаны мною.

2. В рукописи было много ошибок: незначительные оговорки, исправленные мною без специальных замечаний, ошибки, исправленные и прокомментированные в квадратных скобках, и серьезные ошибки, требующие значительной переделки конструкции (их я обсуждаю в разд. 5.1.1 и 5.2.2). Все эти ошибки вполне поправимы, но так как органы автомата, сконструированные в начальных разделах рукописи, используются в дальнейшем, то многие из этих ошибок распространяются и "усиливаются". В этой связи следует помнить, что рукопись была лишь черновым наброском и фон Нейман разрабатывал конструкцию автомата в процессе работы над ней, оставляя многие ее параметры для дальнейшей детализации.

3. Рукопись недописана. Конструирование автомата доведено в ней до той фазы, когда еще не полностью закончен блок ленты. В гл.5 я показываю, как можно завершить эту конструкцию самовоспроизводящегося автомата фон Неймана.

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

Я благодарен многим людям за их помощь. Покойная г-жа Клара фон Нейман-Экарт предоставила мне информацию о рукописях мужа. От нескольких человек, работавших с фон Нейманом в области вычислительных машин, я получил сведения из первых рук. Это Абрахам Тауб, Герман Голдстайн, покойная Адель Голдстайн и в особенности Джулиан Бигелоу и Стэн Улам. И с Бигелоу и с Уламом фон Нейман часто обсуждал свои работы по теории автоматов, Джон Кемени, Пирс Кетчам, Е. Ф. Мур и Клод Шеннон либо слушали лекции фон Неймана по теории автоматов, либо беседовали с ним на эту тему. Письмо Курта Гёделя в конце лекции 2 части I приводится с его любезного разрешения. Я благодарен многим из моих аспирантов и коллег за техническую помощь, в особенности Майклу Файмену, Джону Ханну, Джеймсу Тетчеру, Стефену Хедетнайми, Фридриху Зуппе и Ричарду Лэингу. Алиса Финней, Карен Брандт, Энн Джекобе и Алиса Р. Бёркс обеспечили редакторскую помощь, а Элизабет Брандт сделала рисунки. Мою редакторскую работу поддерживал Национальный научный фонд. Никто из упомянутых лиц не несет ответственности за эту работу.

Об авторе

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

Крупнейший американский математик, член Национальной академии наук США (1937). В 1926 г. окончил Будапештский университет. С 1927 г. преподавал в Берлинском университете, в 1930–1933 гг. — в Принстонском университете (США). С 1933 г. — профессор Принстонского института перспективных исследований. С 1940 г. — консультант различных военных учреждений (в частности, принимал участие в работах по созданию первой атомной бомбы). С 1954 г. был членом Комиссии по атомной энергии и председателем консультативного комитета ВВС США по баллистическим ракетам.

Основные научные работы Дж. фон Неймана посвящены функциональному анализу и его приложениям к вопросам классической и квантовой механики. Он также автор исследований по математической логике и по теории топологических групп. В последние годы жизни занимался главным образом разработкой вопросов, связанных с теорией игр и теорией автоматов; внес большой вклад в создание первых ЭВМ и разработку методов их применения.