Вы читаете книгу «P не равно NP: Доказательство, которое математики не поймут» онлайн

Часть I. КРИЗИС БЕССУБЪЕКТНОЙ МАТЕМАТИКИ

Глава 1. Неразрешимость: симптом, а не болезнь

1.1. Проблемы Гильберта и программа формализации

В 1900 году на Международном конгрессе математиков в Париже Давид Гильберт, признанный король математического цеха, огласил список из 23 проблем, которые, по его мнению, должны были определить развитие математики на столетие вперед [1]. Это был не просто список задач, а дерзкая, почти высокомерная заявка: математика всемогуща, и скоро у нее будет ответ на любой вопрос. Девизом Гильберта, который позже высекут на его надгробии, было: «Мы должны знать — мы будем знать» [2]. Забавно, что это высекли как раз перед тем, как его программа с треском провалилась.

Самой амбициозной среди поставленных задач была, пожалуй, вторая — проблема непротиворечивости арифметики. Гильберт хотел доказать математическими же средствами, что в математике никогда не возникнет противоречий. Вы не можете доказать, что 2+2=5. Никогда. Это звучало здраво: если уж мы строим Храм Абсолютного Знания, хорошо бы убедиться, что фундамент не сделан из песка [3].

Из этой идеи выросла так называемая программа Гильберта — грандиозный план по полной формализации всей математики. Замысел был дьявольски изящен в своей наивности:

Формализовать: Переписать всю математику на мёртвом, но кристально чистом формальном языке, превратив доказательства в подобие шахматных ходов. Никакой психологии, никакой интуиции, никаких «мне кажется». Только символы и правила их перестановки [4].

Доказать полноту: Показать, что для любого правильно записанного утверждения внутри этой системы машина формального вывода рано или поздно выдаст либо его доказательство, либо его опровержение. Истина становится вердиктом алгоритма.

Доказать непротиворечивость: С помощью финитных, «абсолютно надежных» методов, в которых никто не мог бы усомниться, доказать, что из аксиом системы невозможно вывести 0=1. То есть доказать безошибочность «машины истины» [1][3].

Решить проблему разрешения (Entscheidungsproblem): Найти универсальный, механически исполняемый метод, который для любого математического утверждения определял бы, истинно оно или ложно. Фактически, создать супер-алгоритм, делающий математиков не нужными [5].

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

Живой, сомневающийся, ошибающийся и осознающий субъект — сам Гильберт, его ученики, любой математик — из этой картины мира методично изгонялся. На его место водружался бездушный механический оракул. Ирония в том, что именно попытка построить этот математический рай без субъекта и породила тех демонов, которые мучают науку о вычислениях до сих пор. О том, как ангелы формализма получили по заслугам от Гёделя и Тьюринга, поговорим в следующей главе.

1.2. Теоремы Гёделя о неполноте: первый удар

Пока Гильберт и его школа наводили бюрократический порядок в математике, в Вене подрастал Курт Гёдель — человек, которому суждено было стать Иудой формалистской программы. В 1931 году он опубликовал работу, содержавшую две теоремы, которые не просто пробили брешь в борту корабля Гильберта, а, по сути, показали, что корабль был спущен на воду уже с пробоиной [6].

Первая теорема, или «Всегда найдется то, чего вы не докажете»

Первая теорема Гёделя о неполноте утверждает, что любая формальная система, достаточно мощная, чтобы выразить арифметику (то есть способная оперировать натуральными числами и сложением-умножением), обречена на неполноту [7]. Это не вопрос сложности системы; это её врожденный дефект.

Идея гениальна в своем коварстве. Гёдель показал, как на строгом языке арифметики можно построить утверждение, которое говорит о самом себе: «Это утверждение недоказуемо в данной системе» [8]. Представьте себе робота-судью, который выносит вердикт: «Данное предложение является ложью». Если робот признает его истинным, то он подтверждает собственную лживость. Если ложным — то он опровергает истину. Система, столкнувшись с таким «гёделевским предложением», впадает в ступор. Она не может ни доказать его, ни опровергнуть, не разрушив собственной логической состоятельности. Оно истинно (мы это видим извне системы), но недоказуемо внутри неё [9].

Это был удар под дых «программе Гильберта». Оказалось, что математическая истина — это не просто результат механического вывода из аксиом. Всегда остается «истина вне клетки», которую видит живой субъект, но не видит формальный автомат.

Вторая теорема, или «Дурак с идеальной картиной мира»

Если первая теорема была болезненной, то вторая стала унизительной. Гёдель доказал: ни одна такая система не может доказать собственную непротиворечивость [10].

Гильберт требовал от математиков предъявить финитное доказательство того, что их игра в символы никогда не приведет к 0=1 Гёдель ответил: внутри самой системы это сделать невозможно в принципе. Чтобы доказать непротиворечивость арифметики, вам понадобится более мощная система. А чтобы доказать непротиворечивость той — еще более мощная. И так до бесконечности. Математики, мечтавшие построить Храм Истины на незыблемом фундаменте, вдруг обнаружили, что этот фундамент висит в пустоте, а чертежи здания бесследно исчезли.

И здесь мы подходим к аналогии, которая объясняет это дилетанту лучше любых учебников. Представьте себе спор в социальных сетях. Ваш оппонент — человек с предельно простой, детской картиной мира, состоящей из трёх аксиом вроде «все политики воруют», «во всем виноваты рептилоиды», а его любимый интернет-портал всегда говорит правду.

С точки зрения формальной логики, его система одновременно и полна, и непротиворечива. У него есть простой ответ на любой вопрос — он не страдает от мук гёделевской неполноты, потому что его убогая аксиоматика недотягивает до мощности арифметики. И что самое главное, в рамках его системы, где любое неудобное вам доказательство объявляется «фейком», он совершенно прав, и его картина мира блестяще непротиворечива. Он, как и требовал Гильберт, доказал свою непротиворечивость своими собственными средствами — просто объявив все внешние аргументы несуществующими.

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

Так первый удар по программе изгнания субъекта был нанесен. Оказалось, что сложная система без познающего субъекта — слепа и не может обосновать даже собственную безвредность. А простая и самодостаточная — это и есть тот самый дурак, с которым бесполезно спорить. Программа Гильберта, таким образом, обещала нам либо паралич, либо идиотию.

1.3. Проблема остановки Тьюринга: алгоритмическая неразрешимость

Пока математический мир приходил в себя после гёделевской бомбардировки, за дело взялся Алан Тьюринг. В 1936 году он опубликовал работу, которая добила центральный пункт программы Гильберта — проблему разрешения, — но сделала это настолько элегантно, что математикам оставалось лишь молча страдать [11].

Тьюринг изобрел свою знаменитую машину — абстрактное вычислительное устройство с бесконечной лентой и конечным набором состояний, — пытаясь формализовать не что иное, как работу скучающего клерка. Машина могла читать символы, писать их, двигать ленту туда-сюда и переходить из состояния в состояние [12]. Вся современная компьютерная индустрия, все серверные фермы и смартфоны — это, по сути, потомки представления Тьюринга о том, как выглядит механическое мышление.

Ирония в том, что Тьюринг изобрел эту машину не чтобы создать компьютер, а чтобы доказать: есть вещи, которые она никогда не сможет вычислить [11].

Для решения Entscheidungsproblem — найти универсальный метод, определяющий истинность любого математического утверждения, — Тьюринг сначала показал, что это эквивалентно задаче о том, остановится ли когда-нибудь произвольная программа на произвольном входе [13]. Если бы существовал алгоритм, решающий проблему остановки, то был бы и алгоритм, решающий любую математическую проблему. Мечта Гильберта могла бы сбыться.

А затем Тьюринг продемонстрировал, почему эта мечта несбыточна в принципе. Его доказательство — это логическая ловушка, достойная дзенского коана [14].

Предположим, пишет Тьюринг, что такой волшебный алгоритм HALT(P, I) существует. Вы даете ему на вход программу P и данные I, а он выдает ответ: «остановится» или «не остановится». Раз он существует, мы можем его использовать как деталь для другой программы.

Теперь построим программу-паразита. Назовем ее BUSTER. Она принимает на вход другую программу Q и делает следующее:

Вызывает оракула HALT(Q, Q). То есть спрашивает: «Остановится ли программа Q, если скормить ей саму себя?»

Если оракул говорит «да, остановится», то назло ему уходит в бесконечный цикл.

Если оракул говорит «нет, не остановится», то BUSTER немедленно останавливается.

Программа BUSTER — это логический вандал. Она делает ровно противоположное тому, что предсказывает оракул.

Теперь подставим BUSTER саму в себя. Мы запускаем BUSTER(BUSTER). Спрашиваем оракула: «Остановится ли BUSTER(BUSTER)?»

Попытка первая. Оракул говорит: «Да, остановится». Тогда BUSTER, следуя своему коду, уходит в бесконечный цикл. Оракул ошибся. Попытка вторая. Оракул говорит: «Нет, не остановится». Тогда BUSTER немедленно останавливается. Оракул снова ошибся.

Оракул, предсказывающий поведение любой программы, не может существовать, потому что всегда можно построить программу, которая загонит его в противоречие [15]. Проблема остановки алгоритмически неразрешима. А с ней неразрешима и проблема разрешения Гильберта.

Самое убийственное в доказательстве Тьюринга — это роль наблюдателя. Мы, люди прекрасно видим, что оракул HALT обречен. Мы понимаем противоречие. Мы осознаем, почему BUSTER его взламывает. Но сам алгоритм HALT никогда не сможет этого понять. Он просто машина.

Формальная система, какой бы мощной она ни была, всегда может быть взломана конструкцией, которая использует её собственные правила против неё самой. И тот, кто видит этот взлом, — это не аксиома, не правило вывода, не автомат. Это субъект.

Тьюринг, в отличие от Гильберта, не пытался изгнать субъекта. Он поместил его в центр доказательства — как того, кто способен на рефлексию, на взгляд со стороны, на понимание предела формального [12]. Машина может вычислить что угодно, но она не может вычислить собственную остановку. А субъект — может.

Так второй удар по бессубъектной математике был нанесен. Оказалось, что не только истина (Гёдель), но и само понятие вычислимости (Тьюринг) ускользает от формальной системы, если в неё не включен тот, кто на эту систему смотрит.

1.4. Проблема P vs NP: эффективная неразрешимость

Если Гёдель и Тьюринг имели дело с абсолютными границами познания — можно ли вообще доказать или вычислить нечто, — то проблема P vs NP бьёт куда обиднее. Она не спрашивает, можно ли решить задачу в принципе. Ответ почти всегда «да»: обычный перебор вариантов рано или поздно сработает. Вопрос в том, можно ли решить задачу до того, как Солнце погаснет [16].

Формально проблема P vs NP была сформулирована в начале 1970-х годов, хотя её корни уходят глубже — в работы по математической логике и только зарождавшейся теории вычислений. Класс P (polynomial time) — это задачи, для которых существует алгоритм, работающий полиномиальное время. Удвоился размер входа — время выросло в разумное число раз. Это «хорошие», ручные задачи. Сортировка списка, поиск кратчайшего пути в графе, проверка числа на простоту — всё это P [17].

Класс NP (nondeterministic polynomial time) — это задачи, для которых проверить предъявленный ответ можно быстро, за полиномиальное время. А вот найти этот ответ — вопрос отдельный [18]. Задача коммивояжёра (найти кратчайший маршрут, проходящий через все города), разложение числа на множители, составление школьного расписания без конфликтов, упаковка чемодана — всё это NP [19].

Вопрос «P = NP?» звучит как невинная детская загадка: если решение можно быстро проверить на правильность, можно ли его так же быстро найти? Или быстрая проверка — это насмешка вселенной, которая показывает нам ответ, но отказывается объяснить, как к нему прийти?

Великое переселение народов: NP-полнота

В 1971 году Стивен Кук взорвал ситуацию, доказав теорему, которую математики до сих пор не могут ему простить [20]. Он показал, что задача о выполнимости булевых формул (SAT) является NP-полной. Это означало: если кто-то когда-нибудь найдет полиномиальный алгоритм для одной-единственной SAT, то автоматически все задачи из NP перейдут в P. Буквально. Лавина сойдёт.

За этим последовал каскад открытий. Ричард Карп в 1972 году опубликовал список из 21 классической задачи, доказав их NP-полноту через сведение к SAT [21]. Клика, гамильтонов цикл, задача коммивояжёра, рюкзак — все они оказались эквивалентны в своей вычислительной трудности. Открой метод для одной — и ты решил их все. Именно этот факт превратил проблему P vs NP из технического вопроса в одну из семи «Задач тысячелетия», за решение которой Математический институт Клэя в 2000 году назначил премию в миллион долларов [16].

Деньги лежат до сих пор.

Где здесь Бог? Оракулы и позор метода релятивизации

Самое унизительное в проблеме P vs NP — это не её нерешённость, они терпеливы и столетиями могут ждать решение проблем, а то, что математики не могут доказать даже возможность её решения имеющимися средствами.

В 1975 году Теодор Бейкер, Джон Гилл и Роберт Соловей опубликовали результат, который должен был бы заставить математиков усомниться в самих основаниях своего ремесла [22]. Они показали, что существуют воображаемые миры — так называемые «оракульные» модели вычислений, — в которых P = NP. И одновременно существуют другие, столь же логически непротиворечивые миры, в которых P ≠ NP.

О чём это говорит? О том, что стандартный метод доказательства в теории сложности — метод релятивизации, то есть рассуждение, которое не зависит от конкретных свойств модели, — принципиально бессилен ответить на вопрос P vs NP. Вы можете строить сколь угодно изощрённые конструкции, но если ваше доказательство «переживает» добавление произвольного оракула, оно не решит проблему. Вы просто докажете, что в мире A — да, а в мире B — нет [23].

Это был момент, когда математическое сообщество, ослеплённое верой во всемогущество формальных методов, получило пощёчину от самой логики. Машина формального вывода, которую они строили со времён Гильберта, сказала им: «Ребята, этим инструментом вы тут ничего не сделаете».

Ликбез для тех, кто ещё не бросил читать: что такое оракул и почему его добавление — это проверка на профпригодность

Чтобы понять масштаб катастрофы, устроенной Бейкером, Гиллом и Соловеем, нужно разобраться с терминологией. Математики обожают называть простые вещи сложными именами, чтобы никто не догадался, как всё на самом деле убого. «Оракул» — прекрасный тому пример.

Оракул в теории сложности — это воображаемая чёрная коробочка, которая мгновенно и бесплатно решает какую-то задачу [22]. Вы подсовываете ей вопрос, она — хоп! — и выдаёт ответ, не тратя ни единого вычислительного такта. Это как если бы ваша программа могла позвонить Богу и спросить: «Слушай, а этот конкретный гамильтонов цикл тут есть или как?» — и Бог бы ответил, не требуя за это процессорного времени.

Физически такой коробочки не существует. Но логически ничто не мешает нам её вообразить и рассуждать о классах сложности, которые получаются, если у машины Тьюринга есть доступ к такому чуду. Так появляются классы вроде P с оракулом для задачи A (обозначается P^A) — это задачи, которые можно решить за полиномиальное время, если у вас под столом живёт джинн, мгновенно решающий A [22].

А теперь — момент, ради которого всё это затевалось.

Доказательство «переживает» добавление произвольного оракула, если оно остаётся верным независимо от того, какой именно джинн сидит у вас под столом [23]. Если вы доказали, что P ≠ NP, и ваше доказательство «релятивизуется» (ещё одно словечко, означающее «работает с любым оракулом»), то оно должно работать и в мире, где оракул решает все возможные задачи за одну операцию, и в мире, где оракул бесполезнее калькулятора.

В чём подвох? А в том, что Бейкер, Гилл и Соловей предъявили два конкретных оракула. Для одного из них P = NP (то есть в этом мире быстрая проверка и быстрое нахождение ответа совпадают). Для другого — P ≠ NP (то есть быстрая проверка есть, а быстрого нахождения нет, идите перебирайте) [22].

Если бы существовало релятивизующееся доказательство того, что P = NP, оно бы доказывало это равенство и для того мира, где оно на самом деле неверно. И наоборот: релятивизующееся доказательство того, что P ≠ NP, сломало бы тот мир, где равенство есть. Противоречие.

Иными словами, любой стандартный метод доказательства, который не использует специфику отсутствия оракула в нашем реальном мире, обречён на провал [23]. А почти все методы, которыми математики умеют пользоваться — диагонализация, симуляция, комбинаторные построения — как раз таковы. Они слишком тупы, чтобы заметить разницу между реальностью и фантазией с оракулом.

Это как если бы следователь пытался доказать вину подозреваемого, используя метод, который одинаково хорошо доказывает вину и невиновного. Суд такое «доказательство» выбросит в мусорную корзину. Но математики, в своём высокомерном самолюбовании, десятилетиями пытались решить P vs NP именно такими методами — и только в 1975 году им ткнули носом в то, что их инструментарий непригоден.

Так что оракул — это не просто забавная абстракция. Это унизительный детектор профнепригодности для математического аппарата всей теории сложности. И аппарат этот проверку не прошёл.

Так в чём же проблема?

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

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

Проблема P vs NP, возможно, не решается так долго именно потому, что математики пытаются решить её в языке, который не различает «построено» и «угадано». Они ищут алгоритм там, где его не может быть по определению.

1.5. Общий корень: исключение субъекта из формальной системы

Итак, мы имеем три, казалось бы, разные катастрофы. Гёдель: в любой достаточно сильной системе есть истинные, но недоказуемые утверждения [7]. Тьюринг: нельзя алгоритмически определить, остановится ли произвольная программа [11]. Кук—Карп—Левин: скорее всего, быстрая проверка решения не гарантирует быстрого нахождения оного, и доказать это имеющимися средствами, похоже, невозможно [22].

Математики привыкли думать, что это три отдельные неприятности, как три разных болезни, поразившие организм их науки. Но что, если это не три болезни, а три симптома одной и той же? Что, если общий корень всех трёх катастроф — это методичное, педантичное, доведённое до абсурда исключение познающего субъекта из формальной системы? Акт коллективного самоубийства, растянутый на столетия.

Проследим маршрут этого интеллектуального харакири.

Шаг первый: Декарт. Он совершает гениальное открытие: «Я мыслю, следовательно, я существую». Субъект становится фундаментом достоверности. Казалось бы, вот оно, начало пути к зрелой науке, которая учитывает наблюдателя. Но нет. Математики прочитали Декарта и вынесли из него не важность субъекта, а важность метода. Субъект им понадобился лишь как трамплин, чтобы прыгнуть в объективное, а сам трамплин — за ненадобностью сжечь.

Шаг второй: Ньютон и Лейбниц. Они создают математический анализ — инструмент невероятной мощи. Но посмотрите, как они его строят. Они говорят о «бесконечно малых», о «стремлении к пределу», о «флюксиях». В этом языке ещё слышен шёпот субъекта: процесс, движение, стремление — это то, что происходит с кем-то, кто движется. Но математикам этот шёпот мешает. Им нужна тишина вечных, застывших истин.

Шаг третий: Коши и Вейерштрасс. Они совершают «очищение» анализа. Вон интуицию. Вон движение. Вон «стремление». Вместо живого процесса — мёртвая логика эпсилон-дельта. «Предел» перестаёт быть тем, к чему кто-то стремится, и становится набором символов, которыми жонглируют по формальным правилам [24]. Субъект, наблюдающий процесс, изгнан. Остался автомат для верификации утверждений.

Шаг четвёртый: Фреге, Рассел, Гильберт. Они решают, что анализа недостаточно. Нужно формализовать всё. Вообще всё. Чтобы от математика осталась только функция проверки доказательств, которую можно доверить машине. Математика должна стать игрой в символы по правилам, где смысл не нужен, а истина — это просто свойство синтаксической выводимости [3].

И вот он, результат. Грандиозный проект формализации завершён. В математике больше нет субъекта. И тут-то всё и начинает сыпаться.

Что общего между тремя нашими катастрофами? В каждой из них формальная система сталкивается с явлением, которое она не может «ухватить» именно потому, что исключила того, кто на неё смотрит.

Гёдель строит предложение «Я недоказуемо». Чтобы понять, что это предложение истинно, нужно выйти за пределы системы и посмотреть на неё со стороны [9]. Нужен субъект. Формальный автомат, который просто перекладывает символы по правилам, никогда не поймёт, что гёделевское предложение говорит о нём самом. Он его просто не увидит. Истина ускользает от автомата, но не от субъекта.

Тьюринг строит программу-паразита BUSTER, которая взламывает гипотетический алгоритм HALT. Чтобы построить BUSTER, нужно понять логику HALT и намеренно сделать наоборот. Нужен субъект, который видит систему извне и осознаёт её пределы [14]. Машина HALT не может осознать собственный предел. А Тьюринг — может.

P vs NP. Здесь та же история, но замаскированная под техническую проблему. NP-задача — это задача, в которой условие сформулировано для готового, актуально данного объекта («существует гамильтонов цикл»). P-задача — это задача, в которой условие определяет пошаговый метод построения («на каждом шаге выбирай непройденное ребро»). Первая формулировка не требует субъекта: объект просто есть или нет в платоновском мире. Вторая требует: метод — это то, что кто-то осуществляет во времени [25].

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

Исключение субъекта создало в математике гигантское слепое пятно. В этом пятне исчезло различие между:

— Актуальным и потенциальным (готовым объектом и процессом его построения);

— Родо-видовым определением и конструктивным определением («это есть то-то» против «сделай раз, сделай два»);

— Проверкой и поиском (верификацией сертификата и нахождением оного);

— Существованием и построением (платоническим «есть» и алгоритмическим «получится»).

Математика, построенная на теории множеств с аксиомой выбора, — это наука о том, что существует. Она принципиально не различает объекты, которые можно построить, и объекты, которые просто «есть» в силу аксиомы [26]. Но проблема P vs NP — это как раз вопрос о том, совпадают ли эти два класса: то, что можно быстро построить, и то, что можно быстро проверить.

Спрашивать об этом математику, которая не различает «построено» и «существует», — всё равно что спрашивать слепого о цвете обоев. Он может дать ответ, но этот ответ не будет иметь отношения к тому, о чём вы спросили.

Именно поэтому Бейкер, Гилл и Соловей и обнаружили, что стандартные методы бессильны [22]. Стандартные методы — это методы математики, исключившей субъекта. Они не видят разницы между построением и существованием. А значит, они не могут доказать несовпадение того, что для них неразличимо.

Так три величайшие катастрофы математики XX века складываются в одну: исключение субъекта не усилило математику, а ослепило её. Оно породило парадоксы (Гёдель), неразрешимости (Тьюринг) и проблемы, которые невозможно решить имеющимися средствами (P vs NP). Храм Истины, построенный на изгнании того, кто познаёт, оказался храмом с заколоченными окнами. В нём всё верно, всё строго, всё формально — и ничего не видно.

1.6. Парадокс как симптом: система не видит собственных оснований

Итак, мы провели вскрытие. Перед нами труп формалистской мечты, и мы смотрим на него с патологоанатомическим интересом. Что же его убило? Гёдель, Тьюринг и проблема P vs NP — это не убийцы, как могло показаться. Это всего лишь симптомы. Болезнь, сожравшая организм математики изнутри, куда глубже.

Когда система кричит о помощи

Представьте себе человека, который приходит к врачу и жалуется на боль в груди. Врач-формалист диагностирует «проблему боли в груди» и выписывает обезболивающее. Через месяц пациент умирает от инфаркта. Врач записывает в отчёте: «Проблема решена: боль устранена, пациент жалоб не предъявляет».

Именно так математики XX века работали с собственными парадоксами. Они не спрашивали: «Почему система порождает эти противоречия?» Они спрашивали: «Как залатать дыру, чтобы продолжать делать вид, что всё в порядке?»

Бертран Рассел в 1901 году показал, что наивная теория множеств Кантора приводит к противоречию: множество всех множеств, не содержащих себя, одновременно и содержит себя, и не содержит [27]. Это был не мелкий баг — это был крах основания. Математики бросились латать: Рассел и Уайтхед написали трёхтомник «Principia Mathematica», где на доказательство того, что 1+1=2, ушла почти тысяча страниц [28]. Цермело и Френкель придумали аксиоматику ZFC, где множество всех множеств просто объявили вне закона, как будто достаточно таблички «Не влезай — убьёт», и проблема исчезнет [26].

Они устранили парадокс, но не спросили: а почему вообще возникла эта ситуация? Почему наивное, интуитивное, «человеческое» понятие множества привело к противоречию? Не потому ли, что формализация попыталась имитировать работу субъекта, который всегда знает границу между «думать о множестве» и «включать множество в само себя», — но имитировать без субъекта, на голых символах?

Эпименид-критянин говорит: «Все критяне лжецы». Это утверждение не может быть ни истинным, ни ложным, не породив противоречия [29]. Гёдель превратил этот древний парадокс в математический молот и разнёс им программу Гильберта [8]. Но что такое парадокс лжеца? Это утверждение, которое ссылается на само себя. Которое говорит: «Я ложно». Чтобы его оценить, нужен тот, кто стоит вне утверждения и смотрит на него. Нужен субъект.

Математики, исключившие субъекта, оказались беззащитны перед самореференцией. Формальная система не может осмыслить утверждение о самой себе — для этого ей нужен внешний наблюдатель. Но внешний наблюдатель и есть тот самый изгнанный субъект.

В 1922 году Туральф Сколем показал, что любая формальная теория множеств имеет счётную модель, даже если она утверждает существование несчётных множеств [30]. Говоря простым языком: говорят «есть несчётные множества», но на самом деле описывают их таким языком, что внутри этой теории вы никогда не сможете построить «настоящую» несчётность. Несчётность существует только для того, кто смотрит извне системы. Для самой системы её нет.

Это как если бы карта говорила: «На территории есть гора Эверест», а сама карта была бы размером с почтовую марку. Для того, кто смотрит на карту, Эверест реален. Для самой карты — это просто клякса краски определённой формы.

Парадокс — это не ошибка, это сигнал

Общий корень всех этих парадоксов — самореференция, помноженная на отсутствие субъекта. Формальная система, исключившая наблюдателя, не может помыслить собственные основания. Она не может провести границу между собой и миром, который описывает [31].

Парадокс — это крик системы о том, что она наткнулась на свой собственный предел. Это не баг, а фича. Это не ошибка в расчётах, а единственный доступный системе способ сообщить: «Я не знаю, где я заканчиваюсь и начинается реальность. Мне нужен тот, кто на меня смотрит».

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

Результат предсказуем. Система, которая не видит собственных оснований, обречена порождать неразрешимости. Она как робот, который пытается починить сам себя. Он может перебирать свои детали, оптимизировать алгоритмы, но он никогда не узнает, почему он был создан, какие аксиомы заложил в него программист-субъект, и что делать с командой, которая противоречит его базовой логике.

P vs NP как финальный диагноз

Теперь мы можем посмотреть на проблему P vs NP не как на техническую трудность, а как на симптом финальной стадии болезни. Это не просто вопрос о том, можно ли быстро решать задачи, ответы на которые быстро проверяются. Это вопрос о том, может ли формальная система осознать разницу между тем, что ей дано (актуальный объект), и тем, что она должна построить (потенциальный процесс).

Парадокс здесь глубже, чем кажется. Чтобы доказать, что P ≠ NP, математикам нужно показать, что существует класс задач, где быстрая проверка возможна, а быстрое решение — нет. Но чтобы это показать, им нужно различать «проверить» и «решить». А их основной инструментарий — формальные системы типа ZFC — принципиально не различает эти два модуса существования.

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

Математики потратили столетия, чтобы построить совершенную формальную систему. Они изгнали из неё всё человеческое: интуицию, движение, время, субъекта. Они хотели получить абсолютную истину, а получили абсолютную слепоту.

Их система идеально непротиворечива — но только до тех пор, пока не спрашивает о собственных основаниях. Их доказательства безупречны — но только до тех пор, пока не касаются различия между тем, что построено, и тем, что угадано. Их наука — вершина интеллектуального могущества, которая не может ответить на вопрос, почему она работает.

Парадокс, как мы выяснили, — это не ошибка. Это единственный честный голос в этом хоре самообмана. Это крик системы о том, что она умирает без того, кого изгнала.

Глава 2. Математика как наука без наблюдателя

2.1. От Платона до Кантора: торжество актуальной бесконечности

Прежде чем хоронить формалистскую программу, стоит понять, откуда вообще взялась эта странная идея — что математика может обойтись без субъекта. Корни этой идеи уходят так глубоко, что математики предпочитают о них не вспоминать: это портит им репутацию трезвомыслящих прагматиков.

Всё началось с Платона — человека, который был настолько недоволен окружающим миром, что изобрёл запасной. В его философии существует два мира: мир вещей, где всё течёт, портится и умирает, и мир идей, где всё совершенно, вечно и неизменно [32]. Математические объекты — числа, геометрические фигуры, отношения — обитают именно там, в мире идей. Они не создаются математиком. Они открываются, как уже существующие.

Это был гениальный пиар-ход. Объявив математические истины вечными и несотворёнными, Платон разом освободил математиков от необходимости объяснять, откуда берутся их объекты. Они не творят — они созерцают. Они не строят — они припоминают. Математик — это не инженер, а жрец, которому дозволено заглядывать в божественный чертёж [33].

Так в математику вошла идея актуальной бесконечности — бесконечности как завершённого, данного сразу и целиком объекта. Множество всех натуральных чисел не строится шаг за шагом. Оно просто есть — сразу, целиком, со всеми своими элементами. Вам не нужно считать до бесконечности, чтобы работать с бесконечностью. Она уже готова, упакована и ждёт вас на складе платоновского гипермаркета.

У Платона был ученик, который пытался предупредить человечество о грядущей катастрофе. Аристотель различал два вида бесконечности [34]. Потенциальная бесконечность — это процесс, который никогда не заканчивается: можно всегда добавить ещё единицу, можно всегда разделить отрезок пополам. Актуальная бесконечность — это бесконечность как готовая вещь: множество, которое бесконечно сейчас, в настоящем, как завершённый объект.

Аристотель настаивал: математика может пользоваться только потенциальной бесконечностью. Актуальная бесконечность — это философская фикция, источник парадоксов, за которую не стоит хвататься голыми руками [35].

Две тысячи лет математики ворчали, но в основном слушались. Они пользовались бесконечностями, но всегда оговаривались: «это просто способ выразиться», «мы имеем в виду, что процесс можно продолжать сколь угодно долго». Актуальная бесконечность оставалась табу.

Справедливости ради надо признать: попытки говорить о бесконечности конструктивно были. И самые блестящие умы античности демонстрировали, как это делается, не скатываясь в платонический гипноз. Евклид, доказывая бесконечность множества простых чисел, не говорит: «Представьте себе актуально бесконечное множество всех простых чисел». Он говорит: «Возьмите любое конечное множество простых, перемножьте их и прибавьте единицу — получите число, которое либо само простое, либо делится на простое, не входящее в ваше множество. Следовательно, никакое конечное множество не исчерпывает всех простых». Это чистое аристотелевское рассуждение в терминах потенциальной бесконечности: что бы вы ни построили, всегда можно построить ещё. Никакого «множества всех простых чисел» как готового объекта здесь не требуется [40].

Это принципиально иной тип мышления, чем канторовский. Евклид не нуждается в платоновском складе, где «уже лежат» все простые числа. Ему достаточно правила, которое позволяет по любому конечному списку построить следующее. Бесконечность здесь — не объект, а процесс.

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

В конце XIX века Георг Кантор совершил то, что сейчас назвали бы стартап-пивотом: он превратил табу в товар [36].

Кантор создал теорию множеств — математику, которая работает с актуальной бесконечностью напрямую, без уверток и оговорок. Множество всех натуральных чисел — это объект, с которым можно обращаться как с готовым. Более того, Кантор показал, что бесконечностей много. Есть счётная бесконечность (натуральные числа), а есть несчётная (действительные числа). И это не просто фигура речи — это строгое математическое утверждение, доказанное диагональным методом [37].

Математическое сообщество взбесилось. Анри Пуанкаре, светило французской математики, называл теорию множеств «болезнью, от которой математика когда-нибудь излечится» [38]. Леопольд Кронекер, учитель Кантора, публично третировал его как «научного шарлатана» и «развратителя юношества» [39]. Борьба была настолько ожесточённой, что Кантор, человек с неустойчивой психикой, провёл последние годы жизни в клиниках для душевнобольных, переключаясь между математикой и богословием.

Но победил именно он, потому что его теория работала. Она давала результаты. Она позволяла доказывать теоремы, которые без неё были недоступны. А математики, при всех своих претензиях на чистоту, — люди практичные. Если инструмент работает, он будет использован, даже если его философские основания подозрительны.

Торжество канторовской теории множеств было полным и безоговорочным. К началу XX века математика перешла на язык множеств. Аксиоматика ZFC стала стандартом. Актуальная бесконечность из philosophia non grata превратилась в рабочую лошадку, на которой ездят, не задавая вопросов.

Но цена этого триумфа оказалась чудовищной — и мы её уже видели в первой главе.

Во-первых, актуальная бесконечность стёрла различие между «построено» и «существует». В платоновском мире все объекты уже есть. Математик их не создаёт — он их находит. А раз так, то нет нужды в методе построения. Достаточно доказательства существования. Аксиома выбора, одна из самых спорных аксиом ZFC, говорит: из любого семейства непустых множеств можно выбрать по элементу — и плевать, что никакого правила выбора не существует. Объекты выбраны, потому что они «есть» [26]. Это вершина бессубъектной математики: действие без действующего, выбор без выбирающего.

Во-вторых, смазалось различие между потенциальным и актуальным. Алгоритм — это потенциальная бесконечность: процесс, который разворачивается во времени. Сертификат — это актуальная бесконечность: готовый объект, предъявленный для проверки. Но для математики на ZFC и то и другое — просто множества. Разница между ними исчезает, как исчезает разница между снимком живого и движением мёртвого.

В-третьих, субъект был окончательно и бесповоротно вычеркнут из онтологии математики. В платоновском мире нет математика. Есть только объекты и отношения между ними. Тот, кто познаёт, стал лишним в науке о познании.

Математики заключили сделку с дьяволом актуальной бесконечности, и дьявол их, как водится, обманул. Он дал им невероятную мощь — возможность работать с бесконечностями как с готовыми объектами. А взамен отобрал зрение — способность видеть разницу между тем, что построено своими руками, и тем, что просто постулировано как существующее.

Именно эта слепота и породила все те парадоксы и неразрешимости, которые мы разбирали в первой главе. Гёдель, Тьюринг, проблема P vs NP — всё это не баги, а фичи мира, в котором актуальная бесконечность победила.

Ирония в том, что математики до сих пор не осознали, что их главная нерешённая проблема — P vs NP — это не технический вопрос. Это счёт, который выставила им реальность за столетия жизни в платонической грёзе. И счет этот, похоже, нечем оплатить — если не вернуть в математику того, кого из неё изгнали.

2.2. Аксиоматический метод: истина без субъекта

Если Платон создал мифологию, а Кантор — бизнес-модель, то аксиоматический метод стал логистической инфраструктурой бессубъектной математики. Это конвейер, по которому платоновские идеи доставляются из мира вечных сущностей в мир публикаций и грантовых заявок. И, как любой конвейер, он спроектирован так, чтобы ни один живой человек не мешал его работе.

От Евклида до Гильберта: как аксиомы перестали быть очевидными

Формально аксиоматический метод старше платонизма. Евклид, написавший свои «Начала» около 300 года до нашей эры, уже пользовался им вовсю: пять постулатов, из которых дедуктивно выводятся теоремы геометрии [41]. Но у Евклида аксиомы — это не произвольные соглашения. Это самоочевидные истины. «Через две точки проходит прямая» — кто же будет с этим спорить? Аксиома для грека — это то, что достойно принятия. Истина, которая видна любому, у кого есть глаза и разум.

Но шли века, и самоочевидность испарялась. Пятый постулат Евклида о параллельных прямых мучил математиков две тысячи лет: слишком сложный, слишком похожий на теорему, слишком… неочевидный. Когда Лобачевский и Бойяи в XIX веке построили геометрию, в которой пятый постулат не выполняется, а через точку проходит бесконечно много параллельных, это был шок [42]. Оказалось, что можно построить другую геометрию, столь же логичную, но с другими аксиомами… неочевидными.

Математики сделали из этого неверный вывод. Вместо того чтобы сказать: «О, так истина зависит от того, кто и как смотрит на мир», они сказали: «О, так истина вообще не зависит от того, кто смотрит. Аксиомы — это просто правила игры. Выбирайте любые, лишь бы они не противоречили друг другу» [43].

Аксиоматический метод в его современном виде — это конвейерная линия. У вас есть сырьё (аксиомы), у вас есть правила обработки (правила вывода), и у вас есть готовая продукция (теоремы). Субъект на этой линии — лишняя деталь, от которой желательно избавиться.

В идеале процесс доказательства должен быть настолько механическим, чтобы его могла выполнять машина Тьюринга — что, собственно, и требовалось по программе Гильберта [3]. Математик-человек — это всего лишь несовершенный прототип автомата для верификации. Он ошибается, устаёт, хочет кушать. Его нужно заменить. А пока не заменили — пусть сидит и проверяет, что цепочка символов, которую он вывел, соответствует формальным правилам.

В этой модели нет места ни интуиции, ни пониманию, ни озарению. Более того, эти человеческие качества объявляются подозрительными. Если вы «интуитивно чувствуете», что теорема верна, но не можете предъявить формальный вывод — вы не математик. Если вы «понимаете», почему утверждение должно быть истинным, но не можете записать это понимание в виде последовательности логических шагов — ваше понимание ничего не стоит [44].

Математика, построенная на аксиоматическом методе, — это математика, в которой эпистемология (учение о том, как мы познаём) полностью оторвана от онтологии (учения о том, что существует). Что существует — решают аксиомы. Как мы об этом узнаём — не важно. Субъект познания исчезает, остаётся только объект познания, подвешенный в логическом вакууме.

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

Аксиоматическая система — это машина. Она перемалывает аксиомы в теоремы. Но она не может выбрать себе аксиомы сама. Аксиомы должны быть заданы извне — субъектом.

Вот он, тот самый изгнанный субъект, который возвращается, как призрак отца Гамлета, в самый неподходящий момент. Вы выгнали его из процесса доказательства — он вернулся в процесс выбора оснований. Вы построили идеально объективную фабрику истины — но кто-то должен был выбрать, на каком сырье эта фабрика работает.

ZFC не упала с неба. Её выбрали люди — Цермело, Френкель, Сколем и другие — на основании своих интуитивных представлений о том, как должны вести себя множества [26]. Аксиома выбора была предметом ожесточённых споров десятилетиями. Её не «вывела» формальная система — её приняли субъекты на основании внематематических, философских аргументов [45].

То же самое с логикой. Классическая логика с законом исключённого третьего — это не божественное откровение. Это выбор, который сделали математики. Интуиционисты во главе с Брауэром предложили другую логику, без закона исключённого третьего, и построили на ней свою, конструктивную математику [46]. Это была полноценная, работающая альтернатива. Но математический мейнстрим выбрал классическую логику — потому что она удобнее, потому что она мощнее, потому что она позволяет доказывать больше теорем. Не потому что она «истиннее», а потому что она практичнее.

Иными словами, в самом сердце аксиоматического метода, замаскированное под объективную необходимость, лежит субъективное решение. Основание самой объективной науки в мире — субъективно.

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

С одной стороны, аксиоматический метод требует исключения субъекта из процесса доказательства. Доказательство должно быть формальным, механическим, проверяемым автоматом.

С другой стороны, аксиоматический метод не может обосновать собственные аксиомы без субъекта. Выбор аксиом — это всегда акт интуиции, веры, философского предпочтения. Это человеческое, слишком человеческое действие.

Математики решили эту проблему простым способом: они о ней забыли. Они договорились, что ZFC — это стандарт, и перестали спрашивать, почему. Они сделали вид, что выбор аксиом — это технический вопрос, решённый раз и навсегда. Субъект, изгнанный из парадной двери, пролез через чёрный ход — и они заперли чёрный ход на замок, а ключ выбросили.

Но проблема никуда не делась. Она просто перешла в хроническую форму. P vs NP — это и есть тот самый вопрос, который аксиоматический метод не может решить, потому что он требует от системы осознать собственные основания. А система, исключившая субъекта, на это не способна.

2.3. Родо-видовые определения как единственный язык математики

Если аксиоматический метод — это логистика бессубъектной математики, то родо-видовые определения — это её единственный язык. Математики не просто изгнали субъекта. Они переписали словарь так, чтобы субъекту в нём просто не нашлось грамматической роли.

Аристотель, который, как мы помним, пытался предупредить человечество об опасностях актуальной бесконечности, подарил логике и ещё один инструмент — теорию определения через ближайший род и видовое отличие [47]. Идея проста и изящна. Чтобы определить понятие, вы указываете, к какому более широкому классу (роду) оно принадлежит, а затем называете признак (видовое отличие), который выделяет его среди всех остальных элементов этого класса.

«Человек есть животное (род), обладающее разумом (видовое отличие)». «Квадрат есть прямоугольник (род), у которого все стороны равны (видовое отличие)». Логическая машина работает безупречно: вы берёте готовый, уже существующий класс объектов, и отсекаете от него лишнее, пока не останется ровно то, что вам нужно.

Этот метод идеально подходит для таксономии — наведения порядка в уже существующей куче. Ботаник, классифицирующий растения, или библиотекарь, расставляющий книги по полкам, — вот прообраз мыслителя, вооружённого родо-видовым методом. Он не создаёт новые виды. Он раскладывает по ящикам то, что уже есть.

Математика, особенно после Кантора и торжества теории множеств, превратилась в гигантскую, необозримую библиотеку платоновских объектов. Каждый математический объект — число, функция, пространство, группа — это не процесс, не конструкция, не действие, а готовая вещь, которая лежит на определённой полке и ждёт, пока её оттуда достанут.

А раз все объекты уже существуют в платоновском мире, то единственная задача математика — правильно их классифицировать. Указать их род, указать их видовое отличие — и готово. Определение состоялось.

Возьмём любое современное математическое определение. «Группа — это множество (род), на котором задана ассоциативная бинарная операция, существует нейтральный элемент, и для каждого элемента существует обратный (видовые отличия)». «Топологическое пространство — это множество (род) с выделенной системой подмножеств, замкнутой относительно конечных пересечений и произвольных объединений (видовые отличия)». «Гамильтонов цикл — это подграф (род), в котором каждая вершина имеет степень ровно два и который является связным (видовые отличия)» [19].

Общий шаблон до тошноты предсказуем. Берётся некоторое множество-род, и на него навешиваются условия-отличия. Чем сложнее объект, тем длиннее список отличий. Но суть не меняется: определить — значит отсечь лишнее от уже существующего.

Торжество родо-видового метода было настолько полным, что математики перестали замечать, что они потеряли вместе с альтернативами. А потеряли они, ни много ни мало, саму возможность говорить о процессе.

Посмотрим на два определения.

Эйлеров цикл (родо-видовое определение): Подграф, в котором каждая вершина имеет чётную степень. Всё. Объект определён, его свойства заданы, его можно искать или проверять.

Эйлеров цикл (конструктивное определение): Начни с любой вершины. Иди по непройденным рёбрам, пока можешь. Если вернулся в начало и остались непройденные рёбра — начни новый цикл из вершины, у которой есть непройденные рёбра, и вклей его в уже построенный. Повторяй, пока все рёбра не будут пройдены [48].

Первое определение говорит: «Вот что такое эйлеров цикл». Второе говорит: «Вот как его сделать». Первое классифицирует. Второе порождает. Первое не требует субъекта — объект просто есть или нет. Второе требует субъекта — того, кто начинает, идёт, возвращается, вклеивает.

Математика выбрала первое и забыла второе. Точнее, она сослала второе на кухню, в область «алгоритмов» и «приложений», объявив его не настоящей математикой, а так, инженерной поделкой. Настоящая математика — это та, где определения через род и вид. Где объекты просто есть, а не становятся.

Алгоритм, с точки зрения чистой математики, — это нелегальный иммигрант. У него нет постоянной прописки в платоновском мире. Он не «существует» — он «выполняется». У него есть начало и конец, он разворачивается во времени, он требует действующего лица.

Родо-видовой язык не умеет говорить об алгоритмах прямо. Он может только описать их как готовые объекты: «Алгоритм — это конечная последовательность инструкций…» Но это описание мёртвого алгоритма, алгоритма как текста, а не как процесса. Это как если бы вы определяли музыку как «последовательность знаков на нотном стане» — формально верно, но полностью упускает суть, которая состоит в звучании.

Именно поэтому в математике возникла отдельная дисциплина — теория алгоритмов, — которая долгое время считалась чем-то вроде прикладной математики для бедных. Настоящие математики работали с множествами. Алгоритмисты работали с процессами. И только когда выяснилось, что некоторые алгоритмические вопросы (например, P vs NP) имеют фундаментальное значение, их нехотя пустили в приличное общество.

Но даже сейчас, когда теория сложности вычислений стала респектабельной, её язык остаётся вторичным по отношению к родо-видовому. Класс P определяют не как «задачи, которые можно решить, следуя определённой пошаговой процедуре», а как «множество языков, для которых существует машина Тьюринга, работающая полиномиальное время». Это родо-видовое определение процесса, которое начисто теряет процессуальность.

Математика сама загнала себя в лингвистическую тюрьму. Она разрешила себе только один способ говорить о вещах — через указание рода и видовых отличий. А потом она же сама удивляется, почему некоторые вещи (например, различие между P и NP) не удаётся ухватить в этом языке.

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

То же самое происходит с P и NP. P-задача и NP-задача в родо-видовом определении выглядят почти одинаково: и там и там «существует объект (сертификат), удовлетворяющий таким-то условиям». Разница в том, что в P этот объект строится пошагово, а в NP — угадывается. Но язык родо-видовых определений не различает «построено» и «угадано». Для него и то и другое — «существует».

Проблема P vs NP не решается так долго не потому, что она сложна. Она не решается, потому что она буквально невыразима в том языке, на котором математики пытаются её решать [49].

Ирония судьбы: Аристотель, который подарил логике инструмент родо-видовых определений, прекрасно понимал его ограниченность. Для него определение через род и вид было лишь одним из способов познания — подходящим для классификации уже известного, но не для открытия нового. Рядом с этим методом у него существовал другой — учение о четырёх причинах, включая действующую причину (то, что производит изменение) и целевую причину (то, ради чего изменение происходит) [50].

Математика взяла у Аристотеля только удобную часть — родо-видовой классификатор — и выбросила всё, что связано с причинами, процессами, целями. Она оставила себе скелет и избавилась от мышц и нервов. Неудивительно, что этот скелет не может ходить.

2.4. Аксиома выбора: легализация неконструктивного

Если родо-видовые определения — это язык бессубъектной математики, а аксиоматический метод — её логистика, то аксиома выбора — это её вишенка на торте. Или, если угодно, её гнилая сердцевина, которую математики старательно покрывают сахарной глазурью формальных обоснований. Это принцип, который позволяет утверждать существование объектов, не предъявляя ни одного примера. Это философский трюк, превращённый в математический закон. Это легализация неконструктивного в самой цитадели точного знания.

Формулировка аксиомы выбора настолько проста, что неподготовленный человек даже не заподозрит подвоха. Звучит она так: «Для любого семейства непустых множеств существует функция, которая выбирает по одному элементу из каждого множества этого семейства» [51]. Функция выбора. Берёт из каждой коробки по конфетке. Что может быть естественнее?

Если у вас есть конечное число конечных коробок, то никакой аксиомы не нужно. Вы просто подходите к каждой, запускаете руку и берёте что-нибудь. Это конструктивный процесс: вы знаете, что делать, вы делаете это шаг за шагом, и в конце у вас в руках — ровно по одному предмету из каждой коробки.

Проблемы начинаются, когда коробок бесконечно много. Или когда в коробках лежат объекты, между которыми вы не можете провести различие. Или когда у вас нет правила, определяющего, что именно брать. Вы не можете «подойти к каждой» — это заняло бы вечность. Вы не можете сказать «возьму самый маленький» — не для всякого множества определено понятие «самый маленький». Вы не можете сказать «возьму любой» — слово «любой» не является алгоритмом [26].

И вот тут на сцену выходит аксиома выбора. Она говорит: не парьтесь. Функция выбора существует. Не надо её строить, не надо предъявлять, не надо объяснять, как она работает. Просто поверьте: она есть. Где-то там, в платоновском мире, где уже лежат все математические объекты, лежит и эта функция. И вы имеете полное право её использовать в доказательствах.

Парадокс Банаха-Тарского, или Во что превращается геометрия с аксиомой выбора

Лучшая иллюстрация того, куда заводит аксиома выбора, — это знаменитый парадокс Банаха-Тарского, доказанный в 1924 году [52]. С помощью аксиомы выбора Стефан Банах и Альфред Тарский доказали, что трёхмерный шар можно разрезать на конечное число кусков, а затем собрать из этих кусков два шара, каждый из которых идентичен исходному. Без пустот. Без растяжений. Без изменения плотности. Просто переложили куски — и из одного шара получилось два.

Это не фокус. Это строгая математическая теорема, доказанная в ZFC. Если вы принимаете аксиому выбора, вы обязаны принять и то, что удвоение объёма — это просто вопрос правильной перегруппировки.

Разумеется, куски, на которые разрезается шар, невообразимо сложны. Они не измеримы в смысле Лебега — у них нет объёма [53]. Их нельзя предъявить физически. Их нельзя даже вообразить в виде чего-то, что можно «разрезать ножом». Это чисто платонические объекты, которые «существуют» только потому, что так сказали.

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

Эрнст Цермело и спор, который всё расставил по местам

Аксиома выбора вошла в математику не через парадную дверь, а через чёрный ход — и с грандиозным скандалом. В 1904 году Эрнст Цермело, пытаясь доказать теорему о том, что любое множество может быть вполне упорядочено, сформулировал принцип, который позже стал известен как аксиома выбора [54].

Реакция была мгновенной и яростной. Эмиль Борель, Анри Лебег, Анри Пуанкаре и другие ведущие математики того времени обрушились на Цермело с критикой, которая сегодня читается как провидческая [45]. Их аргумент был прост: нельзя утверждать существование объекта, для которого не предъявлен метод построения. «Выбрать» элемент из множества — это не магическое заклинание. Это действие. А действие требует действующего.

Особенно язвителен был Борель. Он писал, что аксиома выбора — это не математика, а метафизика. Что рассуждать о бесконечном числе произвольных выборов — это всё равно что рассуждать о Боге, который совершает эти выборы за нас. Что математика не имеет права постулировать существование того, что не может быть построено [55].

Но Цермело победил. Не потому, что его аргументы были сильнее. А потому, что без аксиомы выбора рассыпалась значительная часть математического анализа и теории множеств. Математикам пришлось выбирать: либо отказаться от огромного корпуса уже доказанных теорем, либо принять аксиому выбора вместе со всеми её парадоксальными следствиями. Они выбрали второе — и сделали вид, что это был свободный и осознанный выбор, а не капитуляция перед удобством [51].

Самое ироничное в аксиоме выбора — это то, что она тайком возвращает в математику того самого субъекта, которого математики так старательно изгоняли. Только возвращает его в виде призрака, в виде неузнанного, неназываемого, но необходимого присутствия.

Что такое функция выбора? Это тот, кто выбирает. Это субъект, совершающий акт выбора. В конструктивной математике этот субъект — вы сами. Вы говорите: «Я беру первый элемент», «Я беру наименьший», «Я беру тот, который удовлетворяет такому-то условию». Вы осознаёте, что делаете.

Аксиома выбора говорит: субъект не нужен. Функция выбора существует сама по себе, без выбирающего, как Чеширский кот, который исчез, оставив только улыбку. Но эта бессубъектная функция выбора — фикция. Она не делает ничего. Она просто «есть» — в платоновском смысле, который означает «мы договорились, что она есть, потому что иначе всё сломается».

Математики, сами того не замечая, ввели в свою формальную систему призрака субъекта. Они изгнали живого, осознающего себя наблюдателя — и заменили его мёртвым, бессознательным, но вездесущим «выбирателем», который сидит в каждой аксиоме выбора и совершает бесконечное число актов выбора, не утруждая себя объяснениями, как он это делает [56].

А теперь — самое главное. Если вы приняли аксиому выбора, если вы согласились с тем, что «существует» не обязательно означает «можно построить», то вы потеряли право удивляться тому, что P, возможно, не равно NP.

P vs NP — это вопрос о том, можно ли быстро построить то, что можно быстро проверить. Это вопрос о том, эквивалентны ли конструктивное и неконструктивное существование — в мире полиномиального времени. Но математика в целом уже ответила на аналогичный вопрос — эквивалентны ли конструктивное и неконструктивное существование в принципе. И ответила: нет. Аксиома выбора — это и есть свидетельство о неэквивалентности. Мы постулируем существование объектов, которые не можем построить.

Так почему же математики удивляются, что в мире эффективных вычислений ситуация может оказаться такой же? Что разрыв между «проверить» и «найти» может быть фундаментальным, а не временным техническим затруднением?

Они не должны удивляться. Они сами создали прецедент. Они сами сказали: да, бывает так, что объект существует, но мы не знаем, как его получить. Аксиома выбора — это их собственная декларация о том, что P ≠ NP в общем случае. Осталось только осознать это применительно к миру полиномиальных вычислений.

2.5. Следствие: математика не различает «построено» и «угадано»

Итог прост, как приговор: современная математика принципиально не различает «построено» и «угадано».

Давайте проведём мысленный эксперимент. Представьте, что вы — математик, и вы доказываете теорему существования. Вы говорите: «Существует объект X, обладающий свойством P». Что именно вы утверждаете? Что вы можете предъявить X? Что вы знаете, как его построить? Что у вас есть метод, алгоритм, рецепт, инструкция? Вовсе нет. Вы утверждаете только одно: предположение о том, что такого объекта нет, приводит к противоречию. И всё.

Это классическое доказательство от противного. Вы не строили X. Вы не знаете, как он выглядит. Вы не можете его предъявить. Вы просто показали, что его несуществование логически несовместимо с вашими аксиомами. И математическое сообщество довольно кивает: доказательство существования состоялось [57].

Но теперь представьте, что вы — не математик, а инженер. Вам нужно построить мост. Вы приходите к начальнику и говорите: «Доказано, что мост существует». Начальник спрашивает: «Где чертежи?» Вы отвечаете: «Чертежей нет. Но предположение об отсутствии моста противоречит законам физики, следовательно, мост где-то есть». Долго ли вы проработаете на этой должности?

Математика, в отличие от инженерии, не требует предъявления объекта. Она удовлетворяется доказательством его существования. И до тех пор, пока математика остаётся игрой в символы на бумаге, это работает. Но как только математика пытается ответить на вопросы о реальном мире — о вычислениях, об алгоритмах, о том, что можно сделать за разумное время, — этот трюк перестаёт работать. Потому что в мире вычислений «существует» без «вот как это построить» — это пустой звук [58].

Философы давно заметили, что слово «есть» в математике употребляется в двух радикально разных смыслах. Первый смысл — конструктивный: «Я построил это, и вот оно». Второй смысл — платонический: «В мире идей это имеется, можете не сомневаться» [59].

В повседневной жизни мы прекрасно различаем эти смыслы. «У меня есть миллион долларов» — это одно. «Где-то в мире существует миллион долларов» — это совсем другое. Ребёнок, играющий в песочнице, интуитивно понимает разницу между «я слепил куличик» и «куличики вообще существуют как класс объектов».

Но математика, изгнавшая субъекта, утратила эту интуицию. Для неё оба «есть» слиплись в один формальный квантор существования: ∃. Этот квантор не различает, построен объект или угадан, предъявлен или постулирован, найден перебором или схвачен интуицией. Он говорит только: «В универсуме рассмотрения найдётся такой элемент». А как он там оказался — не важно.

Именно эта неразличимость и породила трагикомическую ситуацию с проблемой P vs NP. Вспомним формальные определения.

Класс P — это класс задач, для которых существует детерминированная машина Тьюринга, решающая задачу за полиномиальное время [17]. Класс NP — это класс задач, для которых существует недетерминированная машина Тьюринга, принимающая язык за полиномиальное время, или, что эквивалентно, существует полиномиальный верификатор [18]. В обоих случаях ключевое слово — «существует». Тот самый слепой, неразличающий квантор ∃.

В P этот квантор скрывает построение. Машина, решающая задачу, — это конструктивный объект. Мы можем написать её код, запустить его и наблюдать, как она пошагово приходит к ответу. В NP этот же квантор скрывает угадывание. Недетерминированная машина «угадывает» правильный переход. Верификатор получает уже готовый сертификат извне.

Но формально, на языке ZFC, эти два «существует» выглядят одинаково. Оба утверждают существование некоторого конечного объекта (машины или сертификата). И математика, вооружённая только своим родо-видовым языком и своим неразличающим квантором, не может увидеть разницу между ними [60].

Хуже того: эта слепота институционализирована. Она встроена в саму ткань математического образования и математической практики. Студентов учат, что доказательство существования — это полноценный результат. Что конструктивное и неконструктивное доказательства равноценны. Что предъявить объект и доказать, что он не может не существовать, — это одно и то же.

А потом эти же студенты, став профессорами, пытаются решить проблему P vs NP — и не могут понять, почему она не поддаётся. Они перебирают всё более изощрённые комбинаторные методы, строят всё более хитрые диагональные конструкции, изобретают всё более причудливые оракулы. Но они не спрашивают: а правильно ли вообще поставлен вопрос? Не является ли проблема неразрешимой не потому, что она сложна, а потому, что язык, на котором она сформулирована, принципиально не способен ухватить искомое различие?

Это напоминает человека, который ищет ключи под фонарём не потому, что он их там потерял, а потому, что там светлее. Математики ищут решение P vs NP методами, которые не различают «построено» и «угадано», — просто потому, что других методов у них нет. А методы эти принципиально не могут дать ответ, потому что ответ требует именно этого различения.

2.6. Почему математика стала «слепой» к генезису

Мы проследили всю историю болезни. Платон подсадил математику на мир идей. Аристотель пытался предупредить. Кантор сделал актуальную бесконечность респектабельной. Аксиоматический метод превратил доказательство в игру в символы. Родо-видовые определения запретили говорить о процессе. Аксиома выбора узаконила существование без построения.

Остаётся последний вопрос: почему? Почему математика, пройдя такой длинный путь, в итоге оказалась слепа к генезису — к тому, как объекты возникают, строятся, становятся? Почему целая наука, гордящаяся своей строгостью, предпочла иметь дело с мумиями, а не с живыми существами?

Ответов несколько, и ни один не делает математикам чести.

Причина первая: эстетическая трусость

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

Математики, как и все люди, любят красивое. А что может быть красивее, чем вечная, неизменная, кристально чистая истина? Платонический объект прекрасен, как античная статуя: он совершенен, он неподвижен, он не стареет и не портится. Алгоритм же — это что-то суетливое, потное, инженерное. Он копошится, перебирает варианты, жужжит процессором. Он — проза, а математики хотят поэзии [61].

За эту любовь к прекрасному они заплатили зрением. Статуя совершенна, но она не движется. Платонический объект безупречен, но у него нет истории. А генезис — это и есть история. Это рассказ о том, как нечто возникло. И математика, отказавшаяся от рассказа в пользу вечности, перестала понимать, откуда что берётся.

Причина вторая: удобство доказательств

Неконструктивное доказательство почти всегда короче конструктивного. Доказать, что объект существует, не предъявляя его, — это как выиграть спор, не приводя аргументов: достаточно поймать оппонента на противоречии самому себе. Быстро, дёшево, эффектно.

Конструктивное доказательство требует работы. Нужно предъявить метод. Нужно показать, как именно строить объект. Нужно оценить, сколько шагов это займёт. Нужно убедиться, что метод не содержит ошибок. Это долго, это трудно, это не всегда получается.

Математики, как и все люди, предпочитают лёгкие пути. Когда выяснилось, что неконструктивные доказательства позволяют публиковать больше статей, получать больше грантов и быстрее продвигаться по карьерной лестнице, выбор был сделан. Математический мейнстрим перешёл на неконструктивную логику не потому, что она «истиннее», а потому, что она «практичнее» [62].

Аристократический платонизм, презирающий суету построения, обернулся банальным карьеризмом. Чтобы публиковаться, не нужно ничего строить. Достаточно доказать, что существует. А на вопрос «почему?» всегда можно ответить: «Это следует из аксиомы выбора». И никто не спросит с вас чертежи.

Причина третья: страх перед субъектом

Но есть и более глубокая, почти психоаналитическая причина. Генезис — это всегда генезис для кого-то. Процесс построения требует строителя. Алгоритм требует исполнителя. Доказательство как действие требует того, кто доказывает.

Вернуть генезис в математику — значит вернуть субъекта. А субъект — это страшно. Субъект ошибается. Субъект сомневается. Субъект привносит в чистую науку что-то человеческое, слишком человеческое: интуицию, предпочтения, эмоции. Математика, мечтавшая стать абсолютно объективной, не могла допустить такого соседства [44].

Поэтому она избавилась от субъекта, как от ненужного свидетеля. Вместе с субъектом она избавилась и от генезиса — потому что одно без другого не существует. Не может быть процесса без того, кто его осуществляет. Не может быть построения без строителя. Не может быть алгоритма без исполнителя.

Математика предпочла мир, в котором никто ничего не делает. Объекты просто есть. Истины просто открываются. Доказательства просто существуют — как цепочки символов, которые никто не должен читать и понимать. Это мир без времени, без действия, без ответственности. Это мир, в котором математику не за что отвечать — потому что он ничего не создал, а только «открыл» то, что было всегда [63].

Причина четвёртая: успех ценой забвения

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

Математики рассудили просто: если метод даёт результаты, зачем задавать вопросы о его основаниях? Зачем копаться в философии, если можно просто публиковать статьи и получать признание? Прагматизм победил рефлексию [64].

Но у каждого успеха есть цена. Ценой этого успеха стала неспособность ответить на вопрос о P vs NP. Потому что этот вопрос — не о следствиях из аксиом. Он о том, как работает сама математика. Он требует от математики посмотреть на себя со стороны — а это именно то, чему математика сопротивлялась столетиями.

Математика стала слепой к генезису не случайно. Она сама выбрала эту слепоту — по соображениям эстетики, удобства, страха и прагматизма. Она систематически уничтожала в себе всё, что связано с процессом, временем, действием и действующим. Она превратила себя в науку о мёртвых объектах и забыла, что сама когда-то была живым действием познающего субъекта.

Результат этого выбора — перед нами. Неразрешимости. Парадоксы. Проблема P vs NP, которая не поддаётся никаким формальным методам, потому что она сформулирована в языке, который утратил способность различать построенное и угаданное.

Хватит ли у математики смелости признать, что она сама создала эту проблему и сама же должна её решить — вернув в себя то, что изгнала?

Выход из этого тупика — не в том, чтобы придумать ещё более хитрый формальный трюк. Выход — в том, чтобы вернуть в математику различие, которое она сама у себя отняла. Нужен язык, в котором «построено» и «угадано» — это разные категории, а не вариации одного квантора ∃. Нужна математика, которая помнит о субъекте.

Именно это и предлагает гуманитарный метод, к изложению которого мы перейдем в следующей части. Но прежде чем строить новое, мы должны посмотреть, кто уже пытался это сделать до нас — и почему у них не получилось.

Глава 3. Попытки вернуть конструктивность (исторический обзор)

3.1. Интуиционизм Брауэра

Брауэр начал с простого, почти наивного вопроса: что такое математика? И дал ответ, от которого формалистов передёргивало: математика — это не набор теорем о платонических объектах. Математика — это деятельность человеческого ума. Она происходит в сознании математика, а не где-то там, в мире идей. Она строится, а не открывается [65].

Этот тезис звучит почти как буддистская мудрость. Не ищите истину вовне. Истина — это то, что вы конструируете. Математический объект существует только тогда, когда он построен в уме. А до этого момента его просто нет.

Из этого следовал убийственный вывод, которого математическое сообщество не могло простить Брауэру: доказательство существования без предъявления объекта — это не доказательство. Если вы говорите «существует число с таким-то свойством», но не можете его предъявить или хотя бы указать метод его нахождения, — вы не математик. Вы болтун. Вы не построили число, вы просто произнесли заклинание [66].

Брауэр требовал вернуть в математику то, что мы теперь назвали бы гуманитарным критерием: наблюдаемость элементарного действия, однозначность метода, осознание того, что ты сделал. Он не использовал этих терминов, но интуитивно двигался ровно в том же направлении.

Чтобы реализовать свою программу, Брауэр пошёл на шаг, который математики восприняли как акт интеллектуального терроризма. Он отказался от закона исключённого третьего.

Закон исключённого третьего — это логический принцип, гласящий: любое утверждение либо истинно, либо ложно, третьего не дано. На этом принципе держится львиная доля классических математических доказательств. В частности, на нём держится доказательство от противного: предполагаем, что А ложно, приходим к противоречию, значит А истинно.

Брауэр сказал: этот закон работает для конечных множеств, где можно перебрать все варианты. Но для бесконечных множеств он не работает — потому что вы не можете перебрать бесконечность и проверить, что искомый объект нигде не прячется [67]. Доказать, что объекта нет, не значит построить объект. Это значит лишь, что ваша система аксиом не противоречит его существованию. А это разные вещи.

Классический пример — доказательство существования иррациональных чисел a и b, таких что a в степени b рационально. Рассмотрим √2 в степени √2. Если это число рационально — мы нашли искомое. Если иррационально — возведём его в степень √2 и получим 2, что рационально. В любом случае искомые a и b существуют. Но что именно является ответом — первый вариант или второй — мы не знаем. Доказательство не даёт нам метода, оно просто показывает, что ответ есть где-то там.

Для классического математика это нормальное доказательство. Для Брауэра — шулерство. Вы не сказали, какие именно a и b работают. Вы не построили их. Вы просто развели руками и сказали: «Ну они же где-то есть». Интуиционист требует: предъявите. Или хотя бы скажите, как их искать [68].

Программа Брауэра была грандиозна. Он предлагал перестроить всю математику на новых — конструктивных — основаниях. В этой новой математике:

— Каждое доказательство существования должно предъявлять объект или метод его построения.

— Бесконечность понимается только как потенциальная, а не актуальная. Не «множество всех натуральных чисел», а «процесс порождения натуральных чисел, который никогда не заканчивается».

— Логика должна быть интуиционистской — без закона исключённого третьего, без доказательств от противного, без аксиомы выбора [69].

По сути, Брауэр предлагал именно то, к чему мы пришли в нашем анализе проблемы P vs NP. Он требовал математики с субъектом. Математики, которая помнит о генезисе. Математики, в которой «существует» означает «построено».

И что же сделало математическое сообщество? Оно раздавило Брауэра.

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

Гильберт ответил Брауэру с уничтожающей язвительностью, которая сегодня читается как образец академического хамства. Он заявил, что изъять из математики закон исключённого третьего — это всё равно что «запретить боксёру пользоваться кулаками» или «запретить астроному пользоваться телескопом» [70]. Он назвал интуиционизм «попыткой загнать математику в прокрустово ложе философских предрассудков».

Но Гильберт не ограничился риторикой. Он использовал административный ресурс. В 1928 году, когда Брауэр был членом редакционной коллегии престижнейшего журнала «Mathematische Annalen», Гильберт, пользуясь своим влиянием и состоянием здоровья Брауэра (Брауэр болел), организовал его исключение из редколлегии. Формальным поводом стало то, что Брауэр якобы затягивал публикации. Реальной причиной — то, что Гильберт не мог терпеть конкурента [71].

Это был показательный разгром. Математическое сообщество, наблюдавшее за этой дракой, сделало свои выводы. С Гильбертом — слава, гранты, журналы. С Брауэром — изоляция, безработица, забвение. Выбор был очевиден.

Брауэр проиграл по трём причинам.

Во-первых, он был неудобным человеком. Упрямым, резким, не склонным к компромиссам. Он отказывался говорить на языке оппонентов и требовал, чтобы они выучили его язык. В академической политике так не выживают.

Во-вторых, его программа была разрушительной. Если принять интуиционизм всерьёз, то огромная часть математики XX века — весь анализ на основе теории множеств, вся топология с аксиомой выбора, все доказательства от противного — становится недействительной. Это была бы не реформа, а революция. А революций математики боятся больше, чем противоречий.

В-третьих, и это самое важное для нашей темы, — Брауэр не предложил однозначного критерия различимости «построено» и «угадано». Он настаивал на том, что математика должна быть конструктивной, но не дал строгой процедуры проверки конструктивности. Он апеллировал к интуиции, к «человеческому уму», к «деятельности сознания». А это всё ещё слишком размытые понятия для математики, которая хочет быть точной.

Именно здесь гуманитарный метод, который мы обсуждаем в этой книге, может сделать то, чего не смог Брауэр. Он предлагает не просто лозунг «верните субъекта», а конкретную процедуру: наблюдаемость элементарного действия, однозначность метода, превращение желания в потребность через осознание «что я сделал». Это критерии, которые можно применять к конкретным задачам, а не философские пожелания.

Брауэр умер в 1966 году, всеми забытый, в своём доме в голландском Бларикуме. Но его идеи не умерли. Они ушли в подполье, в «параллельную математику», где тихо развивались десятилетиями.

Его ученик Аренд Гейтинг формализовал интуиционистскую логику, показав, что она может быть столь же строгой, как и классическая [72]. Пер Мартин-Лёф создал теорию типов — конструктивную альтернативу теории множеств, где каждое доказательство является программой [73]. Эррет Бишоп в 1967 году опубликовал «Основания конструктивного анализа», где показал, что огромную часть математического анализа можно перестроить на конструктивных основаниях, без аксиомы выбора и закона исключённого третьего [74]. А соответствие Карри-Говарда — формальный мост между доказательствами и программами — стало одним из столпов современной computer science.

Так что Брауэр проиграл битву, но не войну. Его предупреждение было отвергнуто — но не опровергнуто. И сейчас, когда математика упёрлась в проблему P vs NP как в стену, возможно, пришло время перечитать Брауэра заново. Не как исторический курьёз. А как дорожную карту к выходу из тупика.

3.2. Конструктивная математика Маркова и школа Санкт-Петербурга

История конструктивной математики в СССР — это история о том, как идеологическое давление, помноженное на научную честность, иногда даёт парадоксальные результаты. Марксистско-ленинская философия требовала от науки «практической направленности» и «борьбы с идеализмом». Платонизм с его миром идей, где живут математические объекты, был объявлен буржуазным мракобесием. А аксиома выбора — и вовсе поповщиной. Казалось бы, идеальный повод для разгрома всей математики.

Но математики ленинградской школы во главе с Андреем Андреевичем Марковым — сыном того самого Маркова, который придумал цепи, — сделали нечто совершенно неожиданное. Вместо того чтобы проклинать начальство и прятать рукописи под половицу, они построили цельную, логически безупречную альтернативу классической математике, которая не только удовлетворяла требованиям марксистской философии, но и объективно была шагом вперёд по сравнению с интуиционизмом Брауэра.

Брауэр, при всём его героизме, страдал одним недостатком: он был мистиком. Его «интуиция», его «деятельность ума», его «сознание математика» — всё это были понятия, которые невозможно формализовать. Брауэр говорил: «Доказательство — это ментальная конструкция». Но что такое «ментальная конструкция»? Как отличить её от «нементальной»? Где критерий?

Марков и его ученики сделали то, что должны были сделать ещё во времена Брауэра: они выбросили мистику и заменили её строгим, формальным определением конструктивности [75]. Их подход можно сформулировать одной фразой, которая звучит как приговор платонизму: объект существует тогда и только тогда, когда предъявлен алгоритм, который его строит.

Никакого «сознания». Никакой «интуиции». Никакого «мира идей». Только алгоритм. Если вы не можете написать программу, которая за конечное число шагов построит объект, — вы не доказали его существование. Вы просто сотрясли воздух.

Этот подход блестяще решал проблему, которая погубила Брауэра. Брауэр говорил: «Математика — это деятельность ума». Ему отвечали: «А что такое ум?» Брауэр начинал объяснять про интуицию и сознание — и его переставали слушать. Марков сказал: «Математика — это деятельность алгоритма». Ему не могли возразить — потому что алгоритм можно предъявить, запустить, проверить [76].

Конструктивная математика Маркова держалась на трёх принципах, каждый из которых был гвоздём в крышку гроба бессубъектной математики.

Первый принцип: потенциальная осуществимость. Абстракция актуальной бесконечности отвергается. Вместо неё принимается абстракция потенциальной осуществимости: мы можем построить сколь угодно большое натуральное число, но мы никогда не построим «множество всех натуральных чисел» как завершённый объект [77].

Это не техническое ограничение. Это философский выбор. Марков, как когда-то Аристотель, говорит: бесконечность — это не вещь, а процесс. Нельзя работать с «готовой» бесконечностью. Можно работать только с правилами, которые позволяют двигаться всё дальше и дальше.

Второй принцип: отказ от закона исключённого третьего для бесконечных множеств. Здесь Марков наследует Брауэру: утверждение «для всех x выполняется P(x)» не может считаться доказанным, если не предъявлен метод, позволяющий для любого конкретного x проверить, что P(x) истинно. Просто сказать: «Ну не может же быть, чтобы для какого-то x оно было ложно» — недостаточно.

Это отсекает почти все классические доказательства существования, построенные на принципе «если бы объекта не было, мы бы пришли к противоречию». В конструктивной математике Маркова такое рассуждение не проходит. Вы должны предъявить объект. Или хотя бы сказать, как его искать [76].

Третий принцип: алгоритм как критерий существования. Это самое главное. В классической математике существует объект или нет — решают аксиомы. В конструктивной математике Маркова — решает алгоритм. Если вы можете написать программу, которая за конечное число шагов построит объект, — объект существует. Если не можете — извините.

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

Помимо трёх китов, Марков сформулировал ещё один принцип, который стоит особняком и который позже назовут его именем — принцип Маркова [78]. Звучит он так: если алгоритм не может не остановиться, то он остановится.

На первый взгляд, это тавтология. Но за ней стоит глубокий философский смысл. Представьте, что у вас есть программа, и вы доказали, что она не может работать бесконечно — предположение о том, что она никогда не остановится, приводит к противоречию. В классической логике этого достаточно, чтобы утверждать: программа остановится. В интуиционистской логике Брауэра — недостаточно, потому что вы не предъявили момент остановки. Марков говорит: достаточно. Если не-остановка невозможна, то остановка неизбежна. И мы можем утверждать, что программа остановится, даже если не можем сказать, когда именно.

Это был тонкий компромисс между строгим интуиционизмом Брауэра и практическими нуждами реальной математики. Принцип Маркова позволял сохранить часть классических результатов, которые интуиционизм Брауэра безжалостно выбрасывал, и при этом не скатываться обратно в платоническое болото аксиомы выбора.

Западные логики потом долго спорили, является ли принцип Маркова «законным» с точки зрения конструктивизма. Но для самого Маркова и его школы это был не предмет спора, а рабочий инструмент. Они не философствовали о природе истины — они строили работающую математику.

Ленинградская школа конструктивной математики имеет прямое — и убийственное — отношение к проблеме P vs NP. Причём сами марковцы, скорее всего, не думали об этом в таких терминах. Но мы, вооружённые их подходом, можем сформулировать проблему заново.

В классической математике проблема P vs NP звучит так: «Равны ли два класса задач, определённых через квантор существования?» И как мы уже выяснили, ответ на этот вопрос не может быть получен стандартными методами, потому что эти методы не различают типы существования.

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

Обратите внимание: «можно проверить» и «алгоритм строит» — это не два одинаковых «существует». Это два принципиально разных типа утверждений. Первое — это родо-видовое «существует верификатор». Второе — это конструктивное «предъявлен метод построения». Марковская математика различает их по определению.

Более того, марковский критерий потенциальной осуществимости даёт нам инструмент для анализа конкретных задач. Для эйлерова цикла мы можем предъявить алгоритм, который за полиномиальное время строит цикл. Для гамильтонова цикла — не можем. Мы можем только перебирать варианты или угадывать. В классической математике и то и другое — «алгоритмы», просто один быстрый, а другой медленный. В конструктивной математике Маркова между ними — пропасть: один строит, другой угадывает.

Так школа Маркова, сама того не подозревая, создала язык, на котором P ≠ NP — это не гипотеза, а почти что тавтология. Потому что «построить за полиномиальное время» и «проверить за полиномиальное время» — это два разных типа существования, и их несовпадение встроено в саму философию конструктивной математики.

Если Марков и его школа были так хороши, почему же их подход не стал мейнстримом? Ответ до обидного прост. Во-первых, они были в СССР, а СССР проиграл холодную войну — в том числе и в математике. После крушения Союза советская математическая школа была частично ассимилирована западной, частично разорена, и её философские основания были объявлены «идеологическим пережитком» [79].

Во-вторых, конструктивная математика — это всегда ограничение. Она даёт меньше теорем, чем классическая. Меньше — не в смысле качества, а в смысле количества. А математическая индустрия, как любая индустрия, заинтересована в валовом продукте. Классическая математика производит теоремы быстрее и дешевле. То, что часть из них — фикции, существующие только благодаря аксиоме выбора, мало кого волнует. Научная бюрократия считает публикации поштучно, а не на вес конструктивной истины.

В-третьих, конструктивная математика требует от математика больше работы. Неконструктивное доказательство часто короче и проще. Чтобы предъявить алгоритм, нужно попотеть. Чтобы доказать, что алгоритм работает за полиномиальное время, — попотеть вдвойне. Математики, как и все люди, предпочитают лёгкие пути.

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

В самом деле. Что утверждает принцип Маркова? «Если алгоритм не может не остановиться, то он остановится». Звучит как тавтология, как безобидное логическое следствие. Но давайте прочитаем это по частям. «Не может не остановиться» означает: предположение о бесконечной работе приводит к противоречию. Это классическое доказательство от противного — ровно то, с чем боролся Брауэр. Вы не знаете, когда алгоритм остановится. Вы не можете предъявить момент остановки. Вы не можете сказать: «Подожди ещё сто шагов, и он точно встанет». Вы знаете только, что он не может не встать когда-нибудь.

И вы называете это конструктивным знанием?

Принцип Маркова — это та же аксиома выбора, только переодетая в рабочий комбинезон алгоритмиста. Там говорилось: «Функция выбора существует, хоть мы и не знаем, как она работает». Здесь говорится: «Момент остановки существует, хоть мы и не знаем, когда он наступит». Разницы нет. И там, и там вам продают актуальное существование без предъявления, платонический жест в конструктивной упаковке [78]. Это не другое утверждение, это то же самое утверждение, просто адресованное другой аудитории: не теоретико-множественникам, привыкшим к аксиоме выбора, а алгоритмистам, которым аксиома выбора колет глаза, а принцип Маркова — уже нет.

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

Но мы-то с вами уже знаем: маскировка актуальной бесконечности под конструктивность до добра не доводит. Сегодня ты принял принцип Маркова, завтра — аксиому выбора, а послезавтра удивляешься, почему проблема P vs NP не решается. А она не решается именно потому, что математика продолжает протаскивать актуальное существование в конструктивные рассуждения, меняя ему названия, но не меняя сути.

Ленинградская школа, при всех её заслугах, остановилась в шаге от истины. Она нащупала критерий — алгоритм как свидетельство существования, — но не решилась применить его до конца. Она предпочла сохранить часть классической математики ценой сохранения классической слепоты — просто завернув эту слепоту в новую обёртку. А мы теперь расхлёбываем.

Так что школа Маркова осталась маргиналией — уважаемой, но маргиналией. Её результаты вошли в теорию алгоритмов и computer science, но её философия была забыта. А зря. Потому что именно в этой философии — ключ к проблеме P vs NP. Ключ, который математический мейнстрим выбросил, не потрудившись даже понять, от какой двери он был.

3.3. Теория типов Мартин-Лёфа и соответствие Карри-Говарда

Пока советские математики в Ленинграде строили конструктивную математику на фундаменте алгоритмов, а западные математики делали вид, что ничего не происходит, в Стокгольме тихо вызревала самая радикальная альтернатива теории множеств со времён Брауэра. Пер Мартин-Лёф — шведский логик, статистик и философ — сделал то, на что не решился даже Брауэр: он предложил полностью заменить теорию множеств другой формальной системой, в которой субъект не просто допущен в качестве гостя, а прописан в самом синтаксисе.

В классической математике всё является множеством. Число — это множество. Функция — это множество. Отношение — это множество. Даже доказательство — и то, в конечном счёте, всего лишь цепочка символов, которую можно закодировать как множество. Эта онтологическая монотонность очень удобна: если всё — множество, то для всего работают одни и те же аксиомы. Но у этой монотонности есть цена, которую мы уже обсуждали: множество — это родо-видовое понятие. Объект принадлежит множеству или не принадлежит — третьего не дано. А как он туда попал, кто его построил и зачем — это не важно [80].

Мартин-Лёф предложил альтернативу: вместо множеств использовать типы. Тип — это не просто коллекция элементов. Тип — это инструкция по построению этих элементов. Когда вы говорите: «Пусть n — натуральное число», вы в классической математике просто объявляете, что n принадлежит множеству N. В теории типов вы обязаны предъявить, как именно n построено: 0 — это натуральное число (правило введения); если m — натуральное число, то successor(m) — тоже натуральное число (ещё одно правило введения). И никаких других натуральных чисел не существует [81].

Это радикальная смена перспективы. Множество — это мешок, в котором уже лежат все его элементы. Тип — это правило, по которому элементы можно порождать. Множество — актуально. Тип — потенциален. Множество говорит: «Вот что есть». Тип говорит: «Вот как сделать». Мартин-Лёф, сам того, возможно, не подозревая, вернул в математику аристотелевское различие между актуальной и потенциальной бесконечностью — и сделал это на строгом формальном языке [82].

Но настоящая бомба, спрятанная в теории типов, — это не замена множеств типами. Это соответствие Карри-Говарда — открытие, которое показывает, что доказательство теорем и написание программ — это одно и то же.

История этого открытия сама по себе достойна пера драматурга. В 1930-е годы американский логик Хаскелл Карри заметил странную параллель между логическими аксиомами и типами комбинаторов в лямбда-исчислении. В 1960-е годы Уильям Говард, тоже американец, развил эту идею до полноценного изоморфизма: каждой логической связке соответствует типовая конструкция, а каждому правилу вывода — способ построения программы [83]. Но только Мартин-Лёф превратил это наблюдение из курьёза в фундамент целой математической системы.

Суть соответствия проста и убийственна одновременно. Логическая импликация «если A, то B» соответствует типу функции из A в B. Доказать импликацию — значит написать функцию, которая преобразует доказательство посылки в доказательство заключения. Конъюнкция «A и B» соответствует типу пары. Дизъюнкция «A или B» соответствует размеченному объединению. Квантор существования — зависимой паре [84].

Это означает буквально следующее: любое доказательство является программой, а любая спецификация теоремы — типом этой программы. Если вы можете написать программу, тип которой соответствует утверждению теоремы, — вы доказали теорему. Если не можете — не доказали. Точка.

Математики, привыкшие к тому, что доказательство — это текст на естественном языке с вкраплениями формул, восприняли это как акт агрессии. Как это — «доказательство должно компилироваться»? Как это — «проверка доказательства — это проверка типов»? Вы что, предлагаете нам стать программистами? Мы, жрецы платонических истин, должны будем писать код?!

Именно это им и предложили. И они, разумеется, отказались.

Главное преимущество теории типов Мартин-Лёфа перед интуиционизмом Брауэра и даже перед конструктивной математикой Маркова — в том, что конструктивность здесь не является философским пожеланием, пристёгнутым к математике снаружи. Она встроена в сам синтаксис системы.

В классической математике вы можете сказать: «Докажем, что существует объект с таким-то свойством». И доказать это от противного, не предъявляя объекта. В теории типов вы не можете так сказать — потому что тип «существует x, такой что P(x)» определён как тип зависимой пары: вы должны предъявить конкретный элемент a и доказательство того, что P(a) истинно. Если вы не можете предъявить a, вы не можете построить элемент этого типа. Ваше «доказательство» просто не пройдёт проверку типов [81].

Это гениальный ход. Мартин-Лёф не уговаривает математиков быть конструктивными. Он делает неконструктивное рассуждение синтаксически невозможным. Вы не можете написать неконструктивное доказательство в теории типов по той же причине, по которой вы не можете написать программу, которая использует необъявленную переменную: компилятор не пропустит.

Так субъект возвращается в математику — но не как философская метафора, а как программист, пишущий код. Не как «сознание», «интуиция» или «деятельность ума» — а как вполне конкретный человек, сидящий за клавиатурой и набирающий строчки, которые должны скомпилироваться. Теория типов — это математика, в которой без субъекта просто ничего не работает [85].

Если теория типов так хороша, почему же математики до сих пор сидят на ZFC? Ответ одновременно прост и печален.

Во-первых, инерция. Математическое образование во всём мире построено на теории множеств. Все учебники, все курсы, все экзамены предполагают, что математика — это ZFC. Чтобы перевести математику на теорию типов, пришлось бы переписать все эти учебники, переучить всех преподавателей и перепридумать все курсы. Это работа на десятилетия, и никто не хочет за неё браться.

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

В-третьих, — и это самое проблемное, — теория типов не решает проблему P vs NP автоматически. Да, она различает конструктивное и неконструктивное существование. Да, она требует предъявления программы. Но она не говорит, какой длины будет эта программа. Вы можете «предъявить» программу, которая перебирает экспоненциальное число вариантов, — и с точки зрения теории типов это будет корректное доказательство существования. Медленное, но корректное. Теория типов гарантирует конструктивность, но не гарантирует эффективность [86].

И в этом — её ограничение. Как и ленинградская школа, она останавливается в шаге от решения проблемы P vs NP. Она даёт язык, на котором можно говорить о построении. Но она не даёт критерия, отделяющего быстрое построение от медленного. А для этого нужно уже не просто различать «построено» и «угадано». Нужно ещё различать «построено быстро» и «построено медленно». Нужно ввести в математику понятие времени. Понятие усилия. Понятие ресурса.

И здесь мы возвращаемся к гуманитарному методу — потому что именно он, со своим различением предмета и метода, однозначности и неоднозначности, наблюдаемости и фантазирования, может дать недостающий критерий. Но об этом — позже. А пока зафиксируем: Мартин-Лёф и Карри-Говард сделали великое дело. Они показали, что математика может быть конструктивной, не теряя строгости. Они построили мост между логикой и программированием. Им оставалось только понять, что не всякая программа одинаково полезна — и что быстрая программа отличается от медленной примерно так же, как живой тигр от чучела.

3.4. Почему эти подходы не решили проблему P vs NP

Итак, мы рассмотрели три великих попытки вернуть субъекта в математику. Брауэр сказал: математика — это деятельность ума, а не склад платонических объектов. Марков сказал: математика — это деятельность алгоритма, а не созерцание истин. Мартин-Лёф сказал: доказательство — это программа, и если программа не компилируется, то у вас нет доказательства. Казалось бы, после таких заявлений проблема P vs NP должна была рассыпаться сама собой, как карточный домик под порывом ветра.

Не рассыпалась. Почему?

Каждый из трёх подходов совершил один и тот же подвиг: он вернул в математику различие между «построено» и «угадано». И каждый из трёх подходов совершил одну и ту же ошибку: он не различил «построено быстро» и «построено медленно». А проблема P vs NP — это именно о скорости.

Брауэр великолепно расправился с неконструктивными доказательствами существования. Он сказал: предъявите объект. Предъявите метод. Не можете — вы не математик, вы метафизик. Но он ничего не сказал о том, сколько времени должно занимать это предъявление. Интуиционистское доказательство существования может быть экспоненциально сложным — и с точки зрения Брауэра это нормально. Главное, что оно конструктивно. Главное, что объект строится, а не угадывается. А то, что строительство займёт время жизни Вселенной, — это уже не математический вопрос, а инженерный [87].

Марков пошёл дальше: он формализовал конструктивность через понятие алгоритма. Алгоритм либо есть, либо нет. Если есть — объект существует. Если нет — извините. Но Марков, как и Брауэр, не различал быстрые и медленные алгоритмы. Алгоритм полного перебора, работающий экспоненциальное время, — это с точки зрения конструктивной математики Маркова полноценный алгоритм. Он строит объект. Он доказывает существование. То, что его выполнение требует астрономического числа шагов, никого не волнует. Конструктивная математика гарантирует существование построения, но не гарантирует, что это построение можно дождаться [76].

Мартин-Лёф встроил конструктивность в синтаксис. В его теории типов нельзя доказать существование, не предъявив программу. Но — опять то же самое — теория типов ничего не говорит о сложности этой программы. Вы можете написать программу, которая перебирает все возможные сертификаты, пока не найдёт подходящий. Тип у такой программы будет правильный. Компилятор пропустит. Теорема доказана. А то, что программа работает экспоненциально долго, — это проблема hardware, а не mathematics [86].

Три великих революции. Три героических попытки. И один и тот же дефект: слепота к ресурсу. Слепота ко времени. Слепота к тому, что построение построению рознь, и что построение за экспоненциальное время — это практически та же фикция, что и платоническое существование, только растянутая во времени настолько, что никто не доживёт до её завершения.

Почему все три подхода проигнорировали время? Ответ прост и обиднее, чем хотелось бы: потому что время — это не математическая категория. По крайней мере, не математическая в том смысле, какой вкладывают в это слово математики.

В платоническом мире времени нет. Объекты не возникают и не исчезают. Они просто есть — всегда были и всегда будут. В таком мире вопрос «сколько времени займёт построение?» бессмыслен — потому что само понятие «займёт время» предполагает процесс, а процесс предполагает время, а время предполагает субъекта, который ждёт [88].

Математика, изгнавшая субъекта, изгнала и время. У неё нет часов. У неё есть только логическая выводимость: из A следует B, и не важно, сколько шагов вывода потребовалось. Теорема, доказанная за миллион страниц, и теорема, доказанная за три строчки, равноправны. Алгоритм, работающий экспоненциальное время, и алгоритм, работающий линейное время, — оба алгоритмы, и оба «существуют» в платоническом смысле.

Проблема P vs NP — это бунт времени против вечности. Это крик реальности о том, что ресурсы конечны. Это напоминание о том, что математика делается живыми людьми, у которых есть дедлайны, гранты и продолжительность жизни. И ответить на этот крик бессубъектная математика не может — потому что в её языке нет слова «успеть» [89].

Чтобы решить проблему P vs NP, недостаточно различать «построено» и «угадано». Нужно различать «построено быстро» и «построено медленно». Нужна не просто конструктивная математика, а эффективно конструктивная математика. Математика, в которой существование без предъявления эффективного метода — это не существование. Математика, в которой экспоненциальный алгоритм — это не алгоритм, а издевательство над словом «алгоритм».

Брауэр, Марков и Мартин-Лёф сделали первый шаг. Они сказали: предъявите метод. Но они не сказали: предъявите метод, который работает за полиномиальное время. Они не сказали этого, потому что сами ещё не до конца освободились от платонического мышления. Они всё ещё верили, что метод — это да или нет, а не быстро или медленно. Они всё ещё не видели разницы между «можно построить» и «можно построить до завтрака» [90].

Гуманитарный метод, который мы излагаем в этой книге, делает второй шаг. Он говорит: мало предъявить метод. Метод должен быть однозначным — то есть на каждом шагу должно быть ясно, что делать, без перебора вариантов и угадывания. Метод должен быть наблюдаемым — элементарное действие должно быть действием, а не фантазией. И только такой метод превращает желание в потребность, а задачу — в теорию.

Иными словами, гуманитарный метод добавляет к конструктивности требование полиномиальности, не называя его полиномиальностью. Однозначность метода — это и есть критерий, который отсекает экспоненциальный перебор. Перебор — это не метод, это отсутствие метода, замаскированное под метод.

Три великих альтернативных подхода не решили проблему P vs NP, потому что они решали другую проблему. Они решали проблему конструктивности — и решили её блестяще. Но проблема P vs NP — это не проблема конструктивности. Это проблема эффективной конструктивности. Это проблема ресурса. Это проблема времени.

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

Три богатыря остановились в шаге от финиша. Они построили мост между математикой и программированием — но не перешли по нему. Они всё ещё оглядывались на платонический мир, где время не имеет значения. Гуманитарный метод переходит мост до конца. И на той стороне — математика, в которой P не равно NP не потому, что мы это доказали, а потому, что это следует из самого определения метода.

3.5. Необходимость более глубокого основания: субъект и осознание

Мы перебрали всех героев. Брауэр хотел вернуть в математику ум, но не объяснил, что это такое. Марков хотел заменить ум алгоритмом, но не заметил, что алгоритмы бывают экспоненциальными и, следовательно, бесполезными. Мартин-Лёф построил математику, в которой доказательство компилируется, но компилятору всё равно, займёт ли выполнение программы секунду или тепловую смерть Вселенной.

Все трое споткнулись об одно и то же: они пытались починить математику, оставаясь внутри неё. Они меняли аксиомы, переопределяли логику, вводили новые формальные системы — но они не спрашивали, кто будет всем этим пользоваться. А без ответа на этот вопрос любая формальная система — хоть классическая, хоть интуиционистская, хоть типовая — остаётся игрой в символы. Игры могут быть красивыми, увлекательными, даже полезными. Но они не решают проблему P vs NP. Потому что эта проблема — не о символах. Эта проблема — о том, кто эти символы пишет и кто ждёт результата.

Общий дефект всех трёх подходов: они пытались решить проблему субъекта без субъекта. Они хотели, чтобы математика стала честной, конструктивной, осмысленной — но они не хотели впускать в неё живого человека с его ограниченным временем, с его потребностью в результате, с его желанием осознать, что он сделал. Они построили прекрасные формальные системы — и оставили их пустыми, как дома без жильцов.

Здесь мы подходим к центральному пункту, который отделяет гуманитарный метод от всех предыдущих попыток. Марков и Мартин-Лёф заменили субъекта алгоритмом. Это был колоссальный прогресс по сравнению с платонизмом, где субъекта не было вообще. Но это была замена одного неживого на другое.

Алгоритм — это не субъект. Алгоритм не устаёт. Алгоритм не хочет кушать. Алгоритму не нужно домой, к семье. Алгоритм может работать экспоненциальное время и не жаловаться. Алгоритму всё равно, закончится ли вычисление через секунду или через миллиард лет. У алгоритма нет желаний. У алгоритма нет потребностей. У алгоритма нет осознания.

Субъект — это не просто исполнитель инструкций. Субъект — это тот, кто ставит цель. Тот, кто хочет результата. Тот, кто ограничен во времени и в ресурсах. Тот, кто страдает, когда метод не находится. Тот, кто радуется, когда осознаёт, что он сделал.

Именно поэтому никакая формальная система, сколь угодно конструктивная, не может решить проблему P vs NP сама по себе. Потому что проблема P vs NP — это не проблема формальной системы. Это проблема субъекта. Это субъект спрашивает: «Могу ли я найти решение за разумное время?» Это субъект различает «быстро» и «медленно» — не потому, что у него есть формальное определение полиномиальности, а потому, что у него есть жизнь, которая конечна [91].

Чего не хватало Брауэру, Маркову и Мартин-Лёфу? Одного-единственного, но решающего элемента: осознания. Они все говорили о построении. Но никто из них не говорил о том, что построение должно быть осознанным. Что мало построить объект — нужно ещё осознать, как именно ты это сделал. Что метод должен быть не просто предъявлен, а предъявлен с пониманием, почему он работает.

Гуманитарный метод, который мы начинаем излагать в следующей части, ставит осознание в центр. Не просто «алгоритм существует». Не просто «программа компилируется». А «я знаю, что я сделал, чтобы получить этот результат». Это знание превращает желание в потребность. Превращает магию в технологию. Превращает угадывание в метод.

И именно это знание и есть критерий, отделяющий P от NP. P-задача — это задача, для которой метод может быть осознан. NP-задача — это ситуация, для которой метод не осознаётся, сколько ни бейся, потому что его там нет — есть только перебор или чудо.

Три богатыря пытались построить математику без чудес. Это была благородная цель. Но они не заметили, что чудеса можно маскировать под алгоритмы — достаточно сделать алгоритм экспоненциальным. И только осознание, только понимание «что я сделал» позволяет отличить настоящий метод от экспоненциальной имитации. Потому что метод можно осознать и передать другому. А экспоненциальный перебор нельзя осознать — можно только смириться с ним, как с неизбежным злом.

На этом мы заканчиваем историческую часть. Мы видели, как математика изгнала субъекта — и ослепла. Мы видели, как герои-одиночки пытались вернуть субъекта — и не смогли, потому что им не хватило понятия осознания. Теперь наша задача — построить альтернативу, которая не повторит их ошибок.

В следующей части мы изложим гуманитарный метод — философию, которая ставит субъекта в основание математики и даёт строгий критерий, позволяющий отличить P-задачи от NP-задач не через формальные определения классов, а через саму структуру субъективного опыта. Мы покажем, что проблема P vs NP не решается формальными средствами не потому, что она слишком сложна, а потому, что она требует возвращения того, кого математика изгнала.

И здесь же, на самом пороге следующей части, введём важное терминологическое уточнение, которое избавит нас от двусмысленности. До сих пор мы, следуя традиции, говорили «NP-задача». Это было вынужденное подчинение чужому языку. Начиная с этого момента, мы будем называть вещи своими именами.

То, что в классической теории сложности именуется «NP-задачей», с точки зрения гуманитарного метода задачей не является. Задача — это то, у чего есть метод. То, что можно решить, осознавая свои действия шаг за шагом. То, что превращает желание в потребность через предъявление однозначного способа действия.

NP-сущность не такова. У неё нет метода. Есть предмет — свойства, которым должно удовлетворять решение. Есть возможность проверить, удовлетворяет ли предъявленный объект этим свойствам. Но метода построения нет. Он заменён либо перебором, либо угадыванием, либо чудом.

Поэтому в дальнейшем мы будем говорить не «NP-задача», а «NP-ситуация». Это не задача. Это ситуация, в которую попадает субъект: он знает, что ответ существует, он может опознать его когда увидит, но он не знает, как к нему прийти. Он фрустрирован. Он ждёт озарения. Он перебирает варианты. Он надеется на чудо.

Разница между «задачей» и «ситуацией» — это и есть разница между P и NP. Задача имеет метод. Ситуация — нет. Задача решается. Ситуация разрешается — или не разрешается — сама. Задача превращает субъекта в мастера. Ситуация превращает субъекта в игрока.

Так что договоримся: P-задачи и NP-ситуации. Это не игра в слова. Это возвращение слову «задача» его первоначального смысла — того, который математика утратила вместе с субъектом. Задача — это когда ты знаешь, что делать. А когда не знаешь — это ситуация. И первое, чему учит гуманитарный метод, — это честно признаваться себе, в чём ты находишься: в задаче или в ситуации.

Теперь — к делу. К изложению самого метода.

Часть II. ГУМАНИТАРНЫЙ МЕТОД: МАТЕМАТИКА С СУБЪЕКТОМ

Глава 4. Субъект и субъективное явление

4.1. Кто я? Наблюдатель субъективных явлений

Математики привыкли, что доказательства бывают двух сортов. Либо вы доказываете что-то о внешнем мире — о числах, о множествах, о функциях, — и тогда ваше собственное существование не имеет к доказательству никакого отношения. Либо вы не доказываете ничего, а занимаетесь философией, и тогда вас можно не слушать.

Сейчас мы сделаем нечто непростительное с точки зрения обоих этих сортов. Мы докажем теорему о том, кто такой доказывающий. И докажем её строго — методом от противного, которым математики так гордятся. А затем укажем им на то, что доказательство, которое они только что прочитали, является контрпримером к их собственной картине мира. Потому что это доказательство не может быть присвоено никаким формальным автоматом. Оно требует того, кто его читает и узнаёт в нём себя.

Начнём с определений. Они просты настолько, что математику должно стать не по себе от их простоты. Никакой теории множеств. Никаких аксиом выбора. Только то, что непосредственно дано в опыте каждому, кто сейчас читает этот текст.

Субъективное явление — это явление, наблюдаемое одним и только одним субъектом.

Не двумя. Не тремя. Не всем человечеством сразу. Одним. Тем самым, который сейчас читает эти строки. Если явление наблюдаете вы — это ваше субъективное явление. Если его же наблюдаю и я — оно уже не субъективное, потому что нас двое.

Субъект — это тот, кто наблюдает субъективные явления. Носитель этого уникального, неразделяемого опыта. Не «человек вообще». Не «сознание как философская категория». Не «множество всех познающих существ». А конкретный наблюдатель, который прямо сейчас видит буквы на экране или бумаге.

Я — это тот субъект, который задаёт вопрос «Кто я?». Не абстрактное концептуальное «я» из учебников по философии. Не «я» как лингвистическая переменная, которую можно подставить в предложение. А то самое «я», которое произносит или думает это слово. Которое сомневается, читает, понимает или не понимает. Которое является не объектом исследования, а его источником [92].

Заметьте: здесь нет никакой метафизики. Никаких допущений о природе сознания. Никаких споров о том, является ли субъект душой, мозгом или информационным процессом. Есть только констатация: вот это — моё наблюдение, и никто другой не имеет к нему доступа. Это не гипотеза. Это исходный факт, с которого начинается любое познание [93].

Теперь — сама теорема.

Я — наблюдатель субъективных явлений.

Доказательство.

Предположим, что субъективное явление наблюдаю не я. Тогда его наблюдают другие. Но «другие» — это множество. А согласно определению, субъективное явление наблюдается одним и только одним субъектом. Множество наблюдателей противоречит определению. Следовательно, предположение ложно.

Значит, субъективные явления наблюдаю именно я.

Что и требовалось доказать.

Кто доказывает — тот и прав

Всё. Три строчки. Но в этих трёх строчках спрятана бомба, которую математики не смогут обезвредить.

Здесь есть одна тонкость, которую математики, привыкшие к формальным доказательствам, почти наверняка пропустят. А она — ключевая.

Доказательство, которое мы только что провели, не является доказательством о некоем абстрактном «я», которое можно подставить в учебник и забыть. Это доказательство, которое может провести только тот, кто его читает. Я не могу доказать эту теорему за вас. Вы не можете доказать её за меня. Каждый доказывает её сам — про себя.

Когда я говорю: «Я — наблюдатель субъективных явлений», — это утверждение истинно только в том случае, если «я» здесь — это тот, кто его произносит. Если вы скажете: «Я — наблюдатель субъективных явлений», — это будет другое доказательство, с другим субъектом, но с той же самой логической структурой.

Иными словами, перед нами доказательство, которое невозможно обезличить. Его нельзя записать в формальной системе и поручить проверку автомату. Потому что автомат не наблюдает субъективных явлений. У автомата нет «я». Автомат не может провести доказательство от первого лица — он может только манипулировать символами, в которые это доказательство превращено постфактум [96].

Это не недостаток доказательства. Это его суть. Оно показывает, что существуют истины, которые не являются безличными. Которые требуют субъекта — не как абстрактного понятия, а как живого, конкретного, вот этого самого читателя. Математика, которая претендует на то, чтобы быть наукой без субъекта, принципиально не может включить такую истину в свой корпус. Но это не значит, что истины нет. Это значит, что математика слепа к ней.

И вот здесь — самый болезненный для формалистов поворот. Проведённое доказательство не даёт мне права утверждать, что «все люди — наблюдатели субъективных явлений». Этого я не доказывал. Я доказал только про себя. Про того, кто читает эти строки, — должен доказать он сам. Про того, кто не читает, — я вообще ничего не могу утверждать, потому что у меня нет доступа к его опыту.

Это фундаментальная асимметрия, которой нет в классической математике. Там если теорема доказана для одного элемента множества, она часто — через обобщение — доказывается для всех. Здесь этот трюк не проходит. Доказательство для «я» не переносится автоматически на «ты» или «они». Каждый субъект должен провести его самостоятельно.

Математик может возразить: «Но это же солипсизм! Вы утверждаете, что существуете только вы!» Нет. Я не утверждаю, что существую только я. Я утверждаю, что мои субъективные явления даны только мне. О существовании других субъектов я могу догадываться, могу верить в них, могу строить теории — но я не могу наблюдать их субъективные явления. Утверждение «другие субъекты существуют и наблюдают свои субъективные явления» — это не доказанный факт, а разумная и полезная гипотеза, которой мы все пользуемся в повседневной жизни и которая, как мы увидим позже, может быть строго обоснована в рамках гуманитарного метода через понятие меры объективности. Но это именно гипотеза, а не логическая необходимость [95].

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

4.2. Сознание как состояние наблюдения субъективного явления

Итак, мы установили: я — наблюдатель субъективных явлений. Но эта формулировка, при всей её точности, немедленно провоцирует следующий вопрос: а всегда ли я им являюсь? Круглые сутки? Без перерывов и выходных? Или бывают моменты, когда я не наблюдаю субъективных явлений, — и тогда я, выходит, не вполне «я»?

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

Обратимся к личному опыту — тому самому, который математики объявили ненадёжным и исключили из своей науки. Зададим простой вопрос: всё ли время я наблюдаю субъективные явления?

Применим метод, который математики должны оценить: перебор, и ответ станет очевиден каждому, кто когда-либо спал, забывался, отключался. Возможно падал в обморок. В эти моменты я не наблюдаю ничего — ни субъективного, ни объективного, ни какого бы то ни было ещё. Мир исчезает. Субъективные явления прекращаются. А вместе с ними — на время — исчезаю и я как наблюдатель.

Это эмпирический факт, а не философская спекуляция. Каждый может проверить его на себе — достаточно дождаться вечера и лечь спать. Проснувшись, вы сможете засвидетельствовать: был промежуток, в котором вы не наблюдали ничего. Вы не можете сказать, сколько он длился, — потому что в этом промежутке вас как наблюдателя не было. Часы показывают, что прошло восемь часов, но для вас этот промежуток имеет нулевую длительность. Вы закрыли глаза — и открыли их через мгновение, которое для внешнего мира длилось всю ночь [97].

Формалист, желающий поспорить, может сказать: «Но вы же дышали во сне! Вы переворачивались! Ваш мозг работал!» Да, работал. Но я этого не наблюдал. Субъективное явление — это не физиологический процесс. Это то, что дано в опыте. А в опыте сна никаких субъективных явлений нет. Есть провал. Есть ничто. Есть отсутствие наблюдателя [98].

Результат однозначен. Я говорю о себе «я» — то есть выступаю как субъект, как наблюдатель субъективных явлений, — только тогда, когда я нахожусь в сознании. Бессознательно я в «я» не бываю. Сознание — это не просто активность мозга. Это состояние, в котором возможно наблюдение субъективных явлений [100].

Отсюда — определение, которое математикам придётся принять, потому что оно не опирается ни на какую теорию, а только на непосредственный опыт каждого, как аксиому очевидного:

Сознание — это состояние «я наблюдаю субъективное явление».

Не «способность к рефлексии». Не «высшая нервная деятельность». Не «осознание себя как личности». Всё это — следствия или интерпретации. Первично — наблюдение. Сознание — это не субстанция, не функция, не процесс. Это состояние. Состояние, в котором есть субъект и есть явление, которое он наблюдает.

В этом определении нет ничего такого, что математик мог бы отвергнуть как «ненаучное». Оно не ссылается на душу, на Бога, на мировой разум. Оно ссылается только на факт, доступный каждому: иногда я наблюдаю, иногда — нет. Когда наблюдаю — я в сознании. Когда не наблюдаю — не в сознании. Всё остальное — комментарии [101].

Приняв это определение, мы немедленно получаем следствие, которое математики — особенно те, кто работает в теории сложности, — должны повесить у себя над рабочим столом.

Любое познание, любое доказательство, любое решение задачи происходит в сознании. Потому что вне сознания нет субъекта. А без субъекта нет того, кто познаёт. Формальная система может существовать вне сознания — как текст, как последовательность символов, как файл на компьютере. Но она не познаётся вне сознания. Она просто лежит. Познание — это не свойство текста. Это свойство субъекта, который этот текст читает и понимает.

Математика, исключившая субъекта, исключила и сознание. Она сделала вид, что доказательства существуют сами по себе, что истины открываются без того, кто их открывает. Но это фикция, которую мы уже разоблачили в предыдущих главах. Теперь, вооружённые определением сознания, мы можем сказать точнее: математика, исключившая субъекта, работает только по ту сторону сознания. Она имеет дело с мёртвыми объектами. А живое познание — это всегда познание в сознании.

Проблема P vs NP — не исключение. Это проблема, которая может быть решена только в сознании. Вот почему гуманитарный метод начинает с субъекта и сознания. Это не философские украшения. Это необходимые условия для того, чтобы вообще поставить проблему P vs NP так, чтобы она стала разрешимой. Без них — без наблюдателя и его сознания — проблема остаётся игрой символов, которую, как показали Бейкер, Гилл и Соловей, не выиграть стандартными средствами.

4.3. Субъект индивидуальный и неиндивидуальный

До сих пор мы говорили о субъекте так, будто это непременно отдельный человек. Индивид. Личность. Гражданин с паспортом. Это было полезное упрощение, но теперь пришло время его разрушить — и посмотреть, как математики попытаются спрятаться за свои формальные определения, когда мы скажем, что субъектом может быть и группа людей, и они сами втайне это знают, просто никогда не осмеливались назвать.