Роман Бабкин - Информационный Завет. Основы. Футурологическое исследование

В 1931 году математик Курт Гёдель ( Kurt Gödel ) доказал, что во всякой сложной (с т. зр. логики и математики) умозрительной системе есть недоказуемые утверждения 9 . Т.е. они содержат такие величины, для которых невозможно придумать алгоритм. Это невычислимые величины.

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

Все эти математические ухищрения кажутся играми разума. Однако, критерий вычислимости (или, как говорят математики, алгоритмической неразрешимости) крайне важен в обычной жизни. Его существование позволяет метеорологам сохранять лицо и надёжно защищать персональные данные 7 .

Алан Тьюринг много размышлял над точным определением понятия «алгоритм». Ведь на проблемы, поставленные Гильбертом и Гёделем, можно посмотреть под другим углом 6 . Что такое вообще «алгоритм»? Можно ли его точно описать? И какие задачи можно решить с его помощью?

В 1936 году Тьюринг в работе «О вычислимых величинах применительно к проблеме разрешения» ( On Computable Numbers, with an Application to the Entscheidungsproblem ) описал универсальное вычислительное устройство ( universal computing machine ) 31 . Подробная схема работы этого гипотетического устройства есть во многих книгах по математике 13 . Я расскажу о сути.

Допустим, вы располагаете какой-либо информацией. Её можно представить в форме последовательности знаков (букв или цифр). Вам нужно преобразовать информацию – что-то вычислить или сделать так, чтобы эту информацию было удобно передать. Тьюринг показал, что, получив от нас алгоритм (или, выражаясь современным языком, «компьютерную программу»), его устройство сделает эту работу.

Например, укажем универсальному вычислительному устройству, как переводить буквы английского алфавита в числа в двоичной системе счисления (напишем команды «Переведи a в 110 0001», «Переведи p в 111 0000» и т.д.). Т.е. дадим машине алгоритм. Если на входе у нас слово apples , то на выходе устройство выдаст: 110 0001_111 0000_111 0000_110 1100_110 0101_111 0011.

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

Однако «способны» не значит «можем».

То, что может, и есть «машина Тьюринга» ( Turing machine ). Абстрактная математическая модель, описывающая, тем не менее, реальный способ отделить вычислимость от невычислимости.

Позже был сформулирован тезис (принцип) Тьюринга-Чёрча ( Church-Turing thesis or principle ): всякая вычислимая функция вычислима машиной Тьюринга. Иначе говоря: если для определенной задачи можно создать алгоритм, по которому машина Тьюринга будет работать, то задача выполнима 17 .

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

Джон фон Нейман ( John von Neumann ) – один из крупнейших математиков XX века. К его достижениям, например, принадлежит строгая математическая формулировка принципа неопределённости – базового тезиса квантовой теории. Формулировки Вернера Гейзенберга ( Werner Heisenberg ) и Эрвина Шрёдингера ( Erwin Schrödinger ) – гуру квантовой механики – стали частными случаями интерпретации фон Неймана 24 .

Если Тьюринг подробно описал, что такое компьютер, то фон Нейман придумал, как именно он должен работать. Он предложил законы, по которым должно существовать современное вычислительное устройство.

В 1946 году в небольшой брошюре «Предварительное рассмотрение логической конструкции электронного вычислительного устройства» ( Preliminary Discussion of the Logical Design of an Electronic Computing Instrument ), написанной совместно Артуром Бёрксом ( Arthur Burks ), Германом Голдстайном ( Herman Goldstine ) и Джоном фон Нейманом, были изложены принципы компьютерной архитектуры (или, как говорили тогда, машинной организации) 15 :

1. «Языком» компьютера является двоичная система счисления (0 и 1).

2. Компьютер работает по программе – алгоритму указаний или команд.