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

Статуя Алана Тьюринга из угольного сланца работы британского скульптора Стивена Кеттла рядом с портретом Тьюринга, который хранится в Национальном музее компьютеров в Блетчли-парке

(источник: Джон Каллас).

Тьюринг также предложил сконструировать огромный компьютер «Бомба», который позволял моделировать работу десяти «Энигм» одновременно. Да, Тьюринг видел дальше своих коллег, и происходило это не потому, что он обучался в лаборатории с новейшим оборудованием, а потому, что он долгое время исследовал границы теоремы Гёделя — прекраснейшего, по его мнению, творения человеческого разума.

* * *

ДИАЛОГ ИЗ ФИЛЬМА «ВЗЛОМАТЬ КОД»

(РЕЖИССЕР ХЕРБЕРТ УАЙЗ, АВТОР СЦЕНАРИЯ ХЬЮ УАЙТМОР, 1996)

Дилли Нокс: Я ознакомился с некоторыми подробностями вашей работы, господин Тьюринг, и должен признаться, что многие из них мне непонятны.

Тьюринг: Меня это не слишком удивляет.

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

Тьюринг: Что именно?

Дилли Нокс: Не знаю, что-нибудь, несколько слов, объясните в общих чертах.

Тьюринг: Несколько слов?

Дилли Нокс: Да.

Тьюринг: В общих чертах?

Дилли Нокс: Да, если это возможно…

Тьюринг: Хорошо. В общих чертах — речь идет об истинном и ложном. Это техническая статья по математической логике, в которой также рассматривается, как трудно отличить истинное и ложное. Люди, то есть многие люди, думают, что в математике всегда известно, что истинно, а что нет, но это не так! И это никогда не будет так! Это проблема, над которой математики работают уже сорок или пятьдесят лет. Как вам это объяснить? Нужно понять, как отличить истинное отложного, понимаете? […]

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

* * *

Постройка «Бомбы», или «Колосса», первого программируемого компьютера, также изготовленного в Блетчли-парке, вписывалась в череду открытий, восходящую как минимум ко второму десятилетию 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. В то время как Бэббидж на смертном одре был убежден, что, проживи он еще несколько лет, и его аналитическая машина стала бы известной всему миру, Байрон и Тьюринг поняли, что прежде чем можно будет сконструировать первый компьютер, необходимо значительно продвинуться в теории алгоритмов. Наибольших размышлений требовал вопрос, какие задачи можно решить с помощью машины Бэббиджа, а какие — нет. Нечто подобное происходит сегодня с квантовыми вычислениями, теория которых заметно отстает от практических результатов, полученных в попытках сконструировать первый квантовый компьютер.

Гениальная идея Тьюринга, позволившая определить границы возможностей компьютеров будущего, заключалась в том, чтобы со всей серьезностью обдумать, что означает «мыслить как машина». Очевидно, что компьютер не обладает ни разумом, ни воображением человека, которые позволяют нам действовать в совершенно незнакомых ситуациях. С другой стороны, машины не устают и не скучают, выполняя трудоемкие вычисления, у них никогда не бывает «плохих дней». Они — машины! Чтобы отличить задачи, которые компьютер не способен решить ввиду технических ограничений (например, потому что время выполнения написанной программы будет сопоставимо с возрастом вселенной), от тех, которые неразрешимы из-за особенностей формулировки самой задачи, Тьюринг описал идеальный компьютер с бесконечным объемом памяти и бесконечным временем выполнения программ. Задача, которую не могла решить эта машина Тьюринга, не поддалась бы самому мощному компьютеру будущего, таким образом, метод, разработанный английским математиком, позволял определить границы возможностей компьютеров.

Вверху — памятная марка, выпущенная в честь столетия со дня рождения Чарльза Бэббиджа. Внизу — табличка у садов Барселоны, посвященных Аде Байрон

(фото: Анна Наварро Дюран).

* * *

ЧИСЛА БЕРНУЛЛИ

В одной из известнейших историй о Карле Фридрихе Гауссе рассказывается, что как-то раз его учитель в начальной школе захотел немного передохнуть и дал ученикам задание сложить все числа от 1 до 100. Учитель не рассчитывал, что юный Гаусс мгновенно найдет ответ, применив метод, который он затем использовал для вычисления суммы чисел от 1 до 1000. Пусть нужно найти сумму всех натуральных чисел, предшествующих числу n. Идея Гаусса заключалась в том, чтобы записать сумму 1 + 2 + … + n в обратном порядке и воспользоваться симметрией ее членов так, как показано ниже:

Читатель легко может убедиться, что если сгруппировать каждое слагаемое с тем, что записано под ним, их сумма всегда будет равна n + 1. Так как этот процесс повторяется n раз, результатом сложения будет n(n + 1). Однако в этой сумме каждое число учитывается дважды: один раз — в первом ряду, один раз — во втором. Следовательно, полученную сумму нужно разделить на два: