Красота в квадрате. Как цифры отражают жизнь и жизнь отражает цифры

Первой крупной теоремой, доказанной с помощью компьютера, стала теорема о четырехцветной карте, или теорема о четырех красках. Мы с вами уже удостоверились, что любой машинальный рисунок может быть двухцветным, другими словами, что мы можем заштриховать его фрагменты так, чтобы две смежные области всегда были разных цветов. В 1852 году проживающий в Лондоне выходец из Южной Африки Френсис Гатри раскрашивал карту графств Англии. Он обнаружил, что для раскраски карты таким образом, чтобы соседние графства имели разные цвета, достаточно четырех красок. Эксперименты показали, что четырех цветов хватает и для того, чтобы раскрасить так любую карту. Однако больше столетия никто не мог это доказать, пока в 1976 году Кеннет Аппел и Вольфганг Хакен из Иллинойского университета не сделали это, воспользовавшись суперкомпьютером для проверки всех вероятных конфигураций карт. Математики отреагировали неоднозначно[175]. В принципе должна существовать возможность проверить каждую строку доказательства. Но компьютер выполнил слишком большой объем вычислений, для того чтобы можно было их все проверить, а это противоречило эталону доказательства теорем, использовавшемуся со времен Евклида. Однако помимо сугубо философских возражений против такого метода доказательства теорем существовали и другие претензии практического плана. В программах всегда есть ошибки. Разве могли Аппел и Хакен быть полностью уверены в том, что в их программе их нет? Нет, не могли. На самом деле в их доказательстве до сих пор находят новые компьютерные ошибки, хотя все обнаруженные ошибки были исправлены. В 1995 году группа исследователей Принстонского университета составила усовершенствованное компьютерное доказательство теоремы о четырехцветной карте. А в 2004 году Джордж Гонтье из исследовательской лаборатории компании Microsoft в Кембридже (Англия) проверил его с помощью специальной программы, определяющей корректность доказательств, хотя для этого ему пришлось перевести все концепции на специальный язык программирования, который понимала эта программа. Но тогда возникает следующий вопрос: разве можно быть уверенным в том, что такая программа-помощник не содержит ошибок? Нет, полной уверенности в этом нет, однако ее уровень все же выше, чем в случае исходных доказательств, поскольку эта программа была многократно протестирована при выполнении многих других задач. В настоящее время доказательство теоремы о четырех красках — одно из наиболее тщательно проверенных в математике.

После первоначального сопротивления автоматизированным доказательствам теорем со временем большинство математиков все же приняли их. Некоторые даже мечтают о том, что однажды все теоремы будут переведены на универсальный компьютерный язык для проверки доказательств, что позволит создать гигантскую формализованную систему, содержащую все доказуемые математические знания, в которой каждое утверждение строго выводится из совокупности базовых строк компьютерного кода. Когда это произойдет, мы все должны, раздевшись донага, прыгнуть в озеро с криками «Бурбаки!».

Компьютеры изменили ход доказательства теорем. Кроме того, они стали катализатором для формирования новой, захватывающей области математики.

10. Соседи по клеткам

Автор совершает путешествие в мир клеточных автоматов. Он пытается понять смысл «Жизни» и беседует с человеком, который ищет вселенные у себя в подвале

В промозглый лондонский день я отправился на встречу с одним человеком, чтобы поговорить о космических кораблях. Пол Чэпмен сидел на террасе итальянского ресторана в темном пальто, а его панама сияла оранжевым цветом под излучением инфракрасного обогревателя. Темные брови нависали над большими очками без оправы, а лицо заросло взлохмаченной седой бородой. Пол принадлежит к единственной в своем роде группе людей, увлекающихся математической игрой под названием Game of Life («Жизнь»). Ему не терпелось рассказать мне о своем последнем открытии.