Надійна система з ненадійних елементів за Джоном фон Нейманом
Надійні машини та ненадійні елементи. Одна з важливих частин роботи, виконаноїфон Нейманом в теорії автоматів, відноситься до проблеми синтезу надійних машин з ненадійних елементів.
Нехай надано безліч елементарних блоків з деякими позитивними ймовірностями неправильного функціонування. Чи можна з цих блоків за допомогою відповідного методу синтезу будувати довільно великі та складні автомати, для яких ймовірність появи помилки на виході піддавалася контролю? Чи можна зробити ймовірність помилки як завгодно малої або хоча б не перевершує деякого фіксованого значення (не залежить від конкретного автомата)?
Мозок людини і тварин дає нам приклад дуже великий і щодо надійної системи, побудованої з індивідуальних компонентів, нейронів, які ненадійні у виконанні операцій, а й у тонких деталях взаємозв'язку. Більше того, добре відомо, що при пошкодженні, нещасному випадку, хворобі і т. д. мозок продовжує функціонувати чудово правильно, навіть якщо уражені його великі області.
Ці факти є сильним контрастом у порівнянні з поведінкою та організацією сучасних обчислювальних машин. Індивідуальні елементи цих машин повинні бути виконані з надзвичайною надійністю, кожен провід повинен бути з'єднаний потрібним чином, і кожна команда в програмі має бути правильною. Будь-яка помилка в елементі, з'єднанні елементів або програмі зазвичай призводить до повного спотворення результатів.Якщо розглядати мозок як машину, то, очевидно, що запобігання помилкам організовано в ньому зовсім інакше, ніж у обчислювальних машинах.
Ця проблема аналогічна проблемі, що виникає в теорії зв'язку, коли потрібно побудувати такі коди передачі інформації, щонадійність повного коду висока навіть у випадках, коли надійність передачі окремих символів мала. Теоретично зв'язку цю проблему можна вирішити відповідним запровадженням надмірності, й у разі необхідно застосувати аналогічні прийоми. Тут недостатньо простого виконання тих самих обчислень багато разів поспіль і вибору значення з більшості. Значення по більшості береться від ненадійних елементів, і так багато разів поспіль - значення по більшості від значень по більшості і т. д. Тут виникає ситуація: хто вартуватиме сторожа.
Дослідження цих проблем фон Нейман розпочав із розгляду формальної структури автомата. Та система, яку він вибрав, аналогічна моделі Мак-Каллоха-Піттса; Схеми складаються з окремих елементів щодо простого типу, пов'язаних між собою. Кожен елемент отримує двійкові сигнали входи від безлічі різних вхідних ліній і видає вихідні двійкові сигнали деяку вихідну лінію. Сигнал на виході з'являється через число одиниць часу після подачі сигналу на вхід. Якби вихідний сигнал був функцією значень вхідних сигналів, був би надійний елемент, який може виконувати операцію і, ні, штрих Шеффера і т.д. Однак якщо вихідний сигнал залежить від вхідних тільки статистично, наприклад, з ймовірністю 1 - є, на виході виходить штрих Шеффера і з ймовірністю е - заперечення цієї операції, є ненадійний елемент. Якщо ж дано необмежену кількість таких ненадійних елементів, наприклад елементів для реалізації штриха Шеффера, чи можна побудувати надійний варіант будь-якого заданого автомата? Фон Нейман показав, що це можна зробити, і проілюстрував це двома різними прийомами. Перший з них, можливо, більш красивий математично, так як він тісно пов'язаний з описаноюпроблемою та близько підходить до проблеми сторожа.
Рішення полягає в конструюванні з трьох ненадійних підсхем і деяких порівнюючих пристроїв однієї більшої та надійнішої підсхеми, що виконує ту ж функцію, що і вихідна підсхема. Виконуючи це для кожного елемента схеми з ненадійними елементами, отримаємо схему з тією ж поведінкою, що й у заданої, але складається з ненадійних елементів.
Перший прийом, як він вказував, страждає на два недоліки. По-перше, остаточна надійність не може бути зроблена довільно високою, а може бути доведена лише до певного рівня є (є залежить від надійності вихідних елементів). Якщо ці елементи дуже низької якості, то рішення навряд чи можна вважати задовільним. По-друге, що важливіше з практичної точки зору, необхідна надмірність у більшості випадків фантастично велика. Число необхідних елементів зростає експоненційно по відношенню до n елементів, необхідних для створення автомату, що моделюється. Оскільки у всіх випадках, що становлять практичний інтерес, n дуже велике, це рішення цінне лише з погляду логічної можливості.
Другий прийом у тому, що фон Нейман називав мульти-трюком. Він полягає в тому, що двійковий вихід в машині представляється не однією лінією, а пучком з ліній, і двійковий вихідний сигнал визначається в залежності від того, багато ліній або навпаки дуже мало ліній несуть значення 1.
Метод синтезу автоматів, заснований на використанні надійних елементів, у цьому випадку замінюється методом, в якому кожна лінія стає пучком ліній, а кожен елемент замінюється підсхемою, яка оперує відповідним чином пучками вхідних і вихідних ліній. Фон Нейман показав, як можна сконструювати такіпідсхеми.
Він також зробив деякі оцінки надмірності, необхідної для досягнення певної надійності. Наприклад, замість одного ненадійного мажоритарного елемента, ймовірність помилки якого дорівнює 1/200, використанням надмірності 60 000 до 1 можна побудувати підсхему, що представляє мажоритарний елемент для пучків і з ймовірністю помилки 10 20 . Зробивши відповідний підрахунок, побачимо, що цей автомат, що має складність і швидкодію мозку, може працювати протягом ста років, зробивши при цьому лише кілька помилок. Іншими словами, щось споріднене до цієї схеми може мати, принаймні, таку ж надійність, як мозок.
Клод Шеннон, Вклад фон Неймана в теорію автоматів, в Сб: Інформаційне суспільство, М., Аст, 2004, с. 11-15.