Том 22. Сон разума. Математическая логика и ее парадоксы

Постройка «Бомбы», или «Колосса», первого программируемого компьютера, также изготовленного в Блетчли-парке, вписывалась в череду открытий, восходящую как минимум ко второму десятилетию XVII века, когда немецкий астроном Вильгельм Шиккард (1592–1635) создал первые «часы для счета» — хитроумный механизм, способный выполнять сложение, вычитание, умножение и деление.

За Шиккардом следовал Блез Паскаль (1623–1662), в девятнадцать лет начавший работу над своей вычислительной машиной, чтобы облегчить труд отца — сборщика налогов в Руане. Его «Паскалина» произвела фурор в аристократических салонах, вызвав удивление ученых и членов знатных семейств. Там же ее увидел и Готфрид Лейбниц (1646–1716). Он был убежден, что «терять время на вычисления, подобно рабам, недостойно выдающихся людей», поэтому неудивительно, что «Паскалина» вызвала у Лейбница большой энтузиазм и желание немедленно ее усовершенствовать. Ученый мечтал создать машину, способную распознавать все истинные высказывания.

«Паскалина», придуманная французским ученым Блезом Паскалем, стала первой вычислительной машиной в истории.

В начале XIX века вычислительные машины Паскаля и Лейбница вдохновили английского математика Чарльза Бэббиджа (1791–1871) и его ученицу Аду Байрон (1815–1852) на исследования по теории вычислений. Для создания аналитической машины (Analytical Engine) Бэббидж и Байрон выделили обязательные элементы всех процессов в информатике. Во-первых, должна существовать программа, указывающая операции, которые нужно выполнить. Она представляет собой ряд инструкций, которые на основе множества входных данных позволяют вычислить результат, возвращаемый пользователю на выходе программы. Например, на вход программы «умножить» подаются пары чисел вида (2, 3), выводом является их произведение — в этом случае 2·3 = 6. Чтобы программа (далее мы будем называть ее алгоритмом) могла быть исполнена, необходимы процессор, выполняющий инструкции, и память, в которой хранятся входные данные, инструкции и все промежуточные расчеты. В аналитической машине Бэббиджа входные данные вводились с помощью перфорированных карт, которые использовались в ткацком станке Жаккара, предназначенном для автоматического создания узоров.

Ада Байрон была дочерью великого английского поэта лорда Байрона и Анабеллы Милбэнк, которую муж называл «королевой параллелограммов», так как она обучалась алгебре и геометрии у главы кафедры Кембриджа. Лорд Байрон оставил семью после рождения Ады, и Анабелла начала обучать дочь наукам с очень раннего возраста. В семнадцать лет девушка познакомилась с Чарльзом Бэббиджем, произошло это на ужине, организованном ее подругой и наставницей Мэри Сомервилл, которая всегда поощряла занятия Ады математикой. Вскоре Ада объяснила Бэббиджу, как можно вычислить числа Бернулли с помощью перфокарт. Эта задача по своей сложности намного превосходила те, которые к тому времени удалось решить изобретателю аналитической машины. С помощью своего метода, позволявшего «ткать алгебраические задачи», Байрон не только написала первую в истории программу, но и показала, что для решения задачи алгоритмически необязательно начинать с нуля. При решении почти всех задач повторялся определенный набор базовых операций, поэтому часто было достаточно скомбинировать уже имеющиеся перфокарты в правильном порядке. Такие базовые операции современные программисты называют подпрограммами.

Используя тот же подход, что и Ада Байрон, Алан Тьюринг смог заложить основы теории алгоритмов в статье «О вычислимых числах в приложении к проблеме разрешения», опубликованной в 1937 году в журнале Proceedings of the London Mathematical Society. В то время как Бэббидж на смертном одре был убежден, что, проживи он еще несколько лет, и его аналитическая машина стала бы известной всему миру, Байрон и Тьюринг поняли, что прежде чем можно будет сконструировать первый компьютер, необходимо значительно продвинуться в теории алгоритмов. Наибольших размышлений требовал вопрос, какие задачи можно решить с помощью машины Бэббиджа, а какие — нет. Нечто подобное происходит сегодня с квантовыми вычислениями, теория которых заметно отстает от практических результатов, полученных в попытках сконструировать первый квантовый компьютер.