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

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

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

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

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

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

* * *

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

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

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

Читатель спросит, сможем ли мы, заменив первые n чисел на первые n квадратов, получить похожую формулу. Применив несколько более сложный метод, можно доказать, что

и что сумма первых n кубов рассчитывается по формуле

В общем случае, k -е число Бернулли связано с коэффициентами, которые появляются в формуле суммы n первых степеней многочлена k -го порядка от переменной n . Этим числам легко дать словесное определение, но сложно вычислить по формуле, поэтому алгоритм, разработанный Адой Байрон, стал огромным шагом вперед.

* * *

Первым успехом Тьюринга стало определение вычислимой функции. Далее всякий раз, когда мы будем говорить о функции, мы будем иметь в виду функцию, определенную на множестве натуральных чисел и принимающую натуральные значения. Напомним, что функция — это не более чем способ сопоставить каждому числу другое число, которое мы будем называть отображением первого. Чтобы лучше понять изложенное ниже, читатель может представить функцию как машину, которая придает форму закладываемому в нее материалу. Так, наша функция превращает число 3 в другое число, которое мы будем обозначать f(3), где f— первая буква латинского слова «функция». Процесс получения f( n ) по известному n может описываться последовательностью алгебраических операций или более сложной словесной формулировкой. Например, если эта функция сопоставляет каждому числу следующее за ним (как вы уже знаете из предыдущих глав, эта функция используется в аксиомах Пеано), то мы можем записать f( n ) = n + 1, и результатом будет f(3) = 3 + 1 = 4. Если же, напротив, функция определяет n -е простое число, то f(3) будет равно 3, а f(4) будет равно 7, так как первыми простыми числами являются 2, 3, 3, 7, 11. В этом случае функция задается словесным описанием, а не простой формулой, определяющей значение функции в каждой точке.