В 1958 году Клод Шеннон, опубликовал статью: Вклад фон Неймана в теорию автоматов / Von Neumann's contributions to automata theory, где в реферативной форме рассказал о результатах коллеги, полученных в 1956 году:
Надёжные машины и ненадёжные элементы. Одна из важных частей работы, проделанной фон Нейманом в теории автоматов, относится к проблеме синтеза надёжных машин из ненадёжных элементов.
Пусть дано множество элементарных блоков с некоторыми положительными вероятностями неправильного функционирования. Можно ли из этих блоков при помощи соответствующего метода синтеза строить произвольно большие и сложные автоматы, для которых вероятность появления ошибки на выходе поддавалась бы контролю? Можно ли сделать вероятность ошибки сколь угодно малой или хотя бы не превосходящей некоторого фиксированного значения (не зависящего от конкретного автомата)?
Мозг человека и животных даёт нам пример очень большой и относительно надёжной системы, построенной из индивидуальных компонент, нейронов, которые ненадёжны не только в выполнении операций, но и в тонких деталях взаимосвязи. Более того, хорошо известно, что при повреждении, несчастном случае, болезни и т. д. мозг продолжает функционировать замечательно правильно, даже если поражены его большие области.
Эти факты представляют сильный контраст по сравнению с поведением и организацией современных вычислительных машин. Индивидуальные элементы этих машин должны быть выполнены с чрезвычайной надёжностью, каждый провод должен быть соединен нужным образом и каждая команда в программе должна быть правильной. Любая ошибка в элементе, в соединении элементов или в программе обычно приводит к полному искажению результатов. Если рассматривать мозг как машину, то, очевидно, что предохранение от ошибок организовано в нём совершенно иначе, чем в вычислительных машинах.
Эта проблема аналогична проблеме, возникающей в теории связи, когда требуется построить такие коды для передачи информации, что надёжность полного кода высока даже в тех случаях, когда надёжность передачи отдельных символов мала. В теории связи эту проблему можно решить соответствующим введением избыточности, и в данном случае нужно применить аналогичные приёмы. Здесь недостаточно простого выполнения одних и тех же вычислений много раз подряд и выбора значения по большинству. Значение по большинству берётся от ненадёжных элементов, и так много раз подряд - значение по большинству от значений по большинству и т. д. Здесь возникает ситуация: кто будет сторожить сторожа.
Исследование этих проблем фон Нейман начал с рассмотрения формальной структуры автомата. Та система, которую он выбрал, аналогична модели Мак-Каллоха-Питтса; схемы состоят из отдельных элементов относительно простого типа, связанных между собой. Каждый элемент получает двоичные сигналы на входы от множества различных входных линий и выдаёт выходные двоичные сигналы на некоторую исходную линию. Сигнал на выходе появляется через целое число единиц времени после подачи сигнала на вход. Если бы выходной сигнал был функцией значений входных сигналов, имелся бы надёжный элемент, который может выполнять операцию и, не, штрих Шеффера и т.д. Однако если выходной сигнал зависит от входных только статистически, например, с вероятностью 10 - 20, на выходе получается штрих Шеффера и с вероятностью е - отрицание этой операции, то имеется ненадёжный элемент. Если же дано неограниченное число таких ненадёжных элементов, например элементов для реализации штриха Шеффера, то можно ли из них построить надёжный вариант любого заданного автомата? Фон Нейман показал, что это можно сделать, и проиллюстрировал это двумя совершенно различными приёмами. Первый из них, возможно, более красив математически, так как он тесно связан с описанной проблемой и близко подходит к проблеме сторожа.
Решение состоит в конструировании из трёх ненадёжных подсхем и некоторых сравнивающих устройств одной более крупной и более надёжной подсхемы, выполняющей ту же функцию, что и исходная подсхема. Проделывая это для каждого элемента схемы с ненадёжными элементами, получим схему с тем же поведением, что и у заданной, но состоящую из ненадёжных элементов.
Первый приём, как он указывал, страдает двумя недостатками. Во-первых, окончательная надёжность не может быть сделана произвольно высокой, а может быть доведена только до определенного уровня є (є зависит от надёжности исходных элементов). Если эти элементы очень низкого качества, то решение едва ли может считаться удовлетворительным. Во-вторых, что более важно с практической точки зрения, требуемая избыточность в большинстве случаев фантастически велика. Число требуемых элементов растет экспоненциально по отношению к числу n элементов, необходимых для создания моделируемого автомата. Так как во всех случаях, представляющих практический интерес, n очень велико, то это решение ценно только с точки зрения логической возможности.
Второй приём состоит в том, что фон Нейман называл мульти-трюком. Он заключается в том, что двоичный выход в машине представляется не одной линией, а пучком из линий, и двоичный выходной сигнал определяется в зависимости от того, много линий или, наоборот, очень мало линий несут значения 1.
Метод синтеза автоматов, основанный на использовании надёжных элементов, в этом случае заменяется методом, в котором каждая линия становится пучком линий, а каждый элемент заменяется подсхемой, которая оперирует соответствующим образом с пучками входных и выходных линий. Фон Нейман показал, каким образом можно сконструировать такие подсхемы.
Он также сделал некоторые оценки избыточности, требуемой для достижения определенной надёжности. Например, вместо одного ненадёжного мажоритарного элемента, вероятность ошибки которого равна 1/200, использованием избыточности в 60 000 к 1 можно построить подсхему, представляющую мажоритарный элемент для пучков и с вероятностью ошибки 1020. Произведя соответствующий подсчёт, увидим, что этот автомат, обладающий сложностью и быстродействием мозга, может работать в течение ста лет, сделав при этом всего несколько ошибок. Другими словами, нечто родственное этой схеме может обладать, по крайней мере, такой же надёжностью, как мозг.
Клод Шеннон, Вклад фон Неймана в теорию автоматов, в Сб.: Информационное общество, М., Аст, 2004 г., с. 11-15.
