Слабое место математики: можно ли доказать всё, что истинно? [Veritasium]

Вот сайт с шаурмой bloks.

[Музыка]

Фундаменте математике есть слабое место, из-за которого мы никогда не сможем знать все наверняка. Всегда будут истинные утверждения, которые нельзя доказать. Никто точно не знает, что это за утверждение, но вероятно, они похожи на гипотезу о числах близнецах. Так называют пары простых чисел, где одно больше другого на 2, например, 11 и 13 или 17 и 19. Чем дальше по числовой прямой, тем реже встречаются простые числа, такие близнецы, и тем более.

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

Списочке "Игра Жизнь", созданная в 1970 году математиком Джоном Конвеем. К сожалению, он умер от COVID-19 в 2020. Жизнь разворачивается на бесконечном поле из квадратных ячеек, каждая из которых либо жива, либо мертва. В игре всего 2 правила: первое — любая мертвая клетка, имеющая 3 соседей, оживает; и второе — любая живая клетка, которая имеет меньше двух или больше трех соседей, умирает.

Вы задаете начальную конфигурацию клеток и, следуя двум правилам, жизнь создает следующее поколение, затем еще одно, и так далее. Это все происходит автоматически. Он мой назвал жизнь "игрой без игроков". Хоть правила и простые, они порождают разнообразное, довольно сложное поведение. Иногда возникают стабильные конфигурации, которые застывают на месте; другие застревают в вечной петле, а некоторые выбегают по полю в бесконечность, как этот глайдер. Многие просто исчезают, но есть те, которые будут расти вечно, создавая все новые живые клетки.

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

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

Вопрос: является ли жизнь каким-то уникальным примером неразрешимости? Нет, есть множество столь же неразрешимых систем: плитка Wanna, квантовая физика, продажа авиабилетов и даже карточная игра Magic.

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

Кантора интересовали множество чисел, например, натуральные — это положительные целые: 1, 2, 3, 4 и так далее, вещественные, включающие дробные — 1/3, 5/2, и иррациональные, такие как корень из 2 по сути; любое число, которое можно представить как бесконечную десятичную дробь. Он задался вопросом: каких чисел больше — всех натуральных или вещественных?

Ответ, вроде бы, очевиден: и тех, и тех бесконечное количество. Так что по идее множества должны быть равными. Чтобы это проверить, Кантор представил бесконечную таблицу, в которой каждому натуральному числу соответствовало бы вещественное от 0 до 1. Так как это все будут просто бесконечные десятичные дроби, неважно, какой из них мы поставим первым, главное, чтобы в списке были все, и не было повторений. Каждому вещественному числу соответствовало целое. Если лишних чисел не осталось, значит множество всех натуральных чисел и вещественных на выбранном отрезке одного размера.

Допустим, мы это проделали. У нас есть бесконечная таблица, в которой каждое целое число выступает как неповторимый порядковый номер каждого вещественного числа. Теперь Кантор предлагает нам придумать еще одно вещественное число. Мы сделаем это следующим образом: прибавим к первой цифре 1 числа единицу, затем единицу к 2 цифры числа, к 3 цифры — 3 числа и так далее по списку. Если попалась девятка, обкатываем до восьмерки. Получившееся вещественное число находится где-то между нулем и единицей, и что самое главное — в нашем списке его точно не было, ведь оно отличается от первого числа первым десятичным знаком, от второго — вторым и так далее до самого конца. От каждого числа в списке оно отличается как минимум одной цифрой — той, что на диагонали.

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

Кантор ввел понятие континуума или несчетного множества, и счетного примеров довольно много. Есть и больших размеров. Работа Кантора стала очередным потрясением для математики. До этого в течение 2000 лет евклидовая геометрия считалась непоколебимым фундаментом. Но на рубеже 19 века Лобачевский и Гаусс открыли неевклидову геометрию, что заставило математиков более пристально изучить основы своей дисциплины.

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

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

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

Гильберт был убежден, что формальная и строгая система доказательств, опирающаяся на теорему, смогла бы решить все математические трудности, скопившиеся за последний век. И большинство специалистов с ним соглашались. "Никто не сможет изгнать нас из рая, который создал Кантор", — писал Гильберт. Но в 1901 году Бертран Рассел указал на серьезную проблему в теории множеств.

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

Если R не содержит себя, оно должно содержать себя. Но если R содержит себя, она, по определению, не должно содержать себя. То есть R содержит себя, если и только если она себя не содержит. Рассел обнаружил так называемый парадокс самоссылки. Вам, наверное, известен другой его вариант. Допустим, есть городок, в котором живут одни мужчины, и действуют очень странные законы о бритье. В частности, закон гласит, что брадобрей должен брить только тех мужчин, что не бреются сами.

Но брадобрей живет в том же городе, и он тоже мужчина. Кто же бреет его? Если он не бреется сам, его должен брить брат бри, но брадобрей не может брить себя. И так как он не бреет тех, кто бреется сам, так что брадобрей должен брить себя, если и только если он не бреет себя. Это противоречит интуитивной.

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

Перенесемся в 60-е годы 20 века: математик Хоанг размышлял о разных способах разложить разноцветную плитку. Условия такие: совмещать можно края одного цвета, но вращать и переворачивать плитку нельзя, только передвигать по плоскости. Вопрос: можно ли по случайному набору плиток сказать, получится ли замостить ими всю плоскость? Получится ли соединить плитки без зазоров до бесконечности? Оказалось, что для произвольного набора плиток нельзя понять, сложится за мощение или нет. Задача неразрешима, прямо как судьба клеток в игре жизнь.

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

Так получается сохранить истинность утверждений, если верны исходные аксиомы и новые. Гильберт хотел получить формальную систему доказательств, систему символов, язык со строгим набором операций. Тогда логические математические утверждения можно перевести на этот язык. Фраза "если бросить книгу, она упадет" превратится в "если A, то B", а тезис "не бывает бессмертных людей" будет выглядеть вот так. Формалисты хотели придать математическим аксиомам форму символических утверждений и установить правила вывода в качестве правил математических операций.

В этой системе Рассел вместе с Уайтом разработали и изложили такую формальную систему в трех томах. Неким принципе "Я — математика", опубликованном в 1913. Это монументальный труд, почти в две тысячи страниц плотного математического текста, и лишь на 762 странице наконец-то приводится доказательство, что 1 плюс 1 равно 2, после чего автор из уха констатирует, что приведенное выше предложение иногда оказывается полезным.

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

Для Гильберта в математике существовало три больших вопроса. Первый — полнота математики, то есть возможно ли доказать любое истинное утверждение, если доказательство у всего, что на самом деле верно. Второй вопрос — непротиворечивость математики: свободно ли оно от противоречий? Если можно одновременно доказать, что A истинное, что не A та же истина — эта проблема, ведь тогда можно доказать что угодно. И третий вопрос — разрешимость в математике: есть ли такой алгоритм, который однозначно скажет, следует ли какой-то вывод из аксиом?

Гильберт был убежден, что на все три вопроса можно ответить "да". На большой конференции тридцатого года Гильберт произнес пламенную речь, в которой говорил об этих вопросах и закончил фразой, которая емко выражает мечту формалистов: "пусть нашим лозунгом будет не игнор обе muse", что значит "мы не узнаем о нечто совершенно ином, мы должны знать и мы будем знать". Эти слова высечены на его надгробии, но к моменту, когда Гильберт произносил эти слова, его мечта уже начала рушиться.

За день до выступления на той же конференции 24-летний логик Курт Гедель рассказывал о том, что он нашел ответ на первый вопрос Гильберта о полноте. Ответ был отрицательным: полная формальная система математики невозможна. Единственным, кто проявил интерес к его рассказу, был Джон фон Нейман, бывший студент Гильберта. Он единственный задавал Геделю уточняющие вопросы.

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

Знак отрицания — это 1, знак "если" — 2, знак "то" — 3. Но если выразить все эти символы с помощью чисел? Как быть с самими числами? Нулю присваивается цифра 6, а если хотите написать единицу, ставите рядом знак "следующее число". Следующее непосредственно за нулем число — это 1.

Чтобы написать 2, нужно поставить рядом с 0, это будет означать двойку. И так вы можете выразить любое целое число. Да, громоздко, но работает. В этом суть всей системы. Итак, нумерация Геделя подходит для всех необходимых знаков и всех чисел, а значит можно записывать уравнение, скажем, "0 равно 0". Вот как это делается.

Берем простые числа, начиная с 2, и возводим каждую в степень, равную номеру элемента уравнения по системе Геделя, то есть 2 в степени 6 на 3 в степени 5 и 5 в степени 6 равно 240 3 миллиона двести сорок три миллиона. Это число Геделя для уравнения "0 равно 0", и такие числа можно получить для абсолютно любого набора символов.

[Музыка]

Нумерация Геделя словно бесконечная колода карт, в которой для любого набора любых символов, записанных в любом порядке, найдется своя карточка с уникальным номером. Красота системы в том, что любой номер можно разложить на простые множители и понять, какие символы он представляет. В этой колоде будут встречаться как истинные утверждения, так и ложные. Но как доказать истинность утверждения? Нужно обратиться к аксиомам, у которых тоже есть свои номера Геделя, образованные всё тем же образом.

Вот, например, аксиома, в которой сказано: "нет следующего числа за любым числом x, равного нулю". Логично, в этой системе нет отрицательных чисел, поэтому 0 не может следовать ни за каким числом. Возьмем эту аксиому, а затем подставим вместо x 0, и получим 1 не равно 0. У нас получилось простейшее доказательство, которое утверждает, что 1 не равно нулю.

Карточка с доказательством, что 1 не равно нулю, имеет свое число Геделя, или мы вычислили его таким же способом. Взяли простые числа: 2 в степени и 3 в степени "1 не равно нулю". И в итоге мы видим огромную цифру в нем — 73 миллиона знаков, если расписывать полностью, так что я оставил его в экспоненциальной форме. И как видите, номера становятся очень большими, поэтому проще будет называть их буквами: например, "число Геделя А", "число Геделя Б", "число Геделя С" и так далее.

Все это понадобилось Гедею, чтобы найти вот эту карточку. Здесь сказано: "нет доказательства для утверждения с числом Геделя G". И вот в чем дело: число Геделя для этой карточки и есть G. То есть здесь говорится, что это утверждение не доказуемо. И во всей бесконечной колоде нет доказательства для этой карты.

Задумайтесь, если утверждение ложно и доказательства есть, то вы доказали, что доказательства нет. Это тупик, парадокс. Это означало бы противоречивость системы. Другой вариант: содержание карточки — истинное утверждение с номером G, что нельзя доказать. Но тогда эта математическая система содержит истинные утверждения, у которых нет доказательств, и такая система не полна. Это и есть теорема Геделя о неполноте.

Он показал, что любая математическая система, способная к простейшим арифметическим вычислениям, всегда будет содержать истинные утверждения, у которых нет доказательства. В сериале "Офис" есть момент, где обыгрывается парадокс самоссылки и доказательства Геделя. Джим: "Мой враг, оказалось, он злейший враг и самому себе". А враг моего врага — мой друг. Так что Джим получается мой друг.

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

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

Остается третий и последний критерий Гильберта — разрешимость математики. Есть ли такой алгоритм, который точно покажет, следует ли какое-либо утверждение из аксиом? В 1936 году Алан Тьюринг нашел способ решить эту задачу, но для этого ему нужно было изобрести современный компьютер.

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

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

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

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

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

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

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

Можно модифицировать H, добавив дополнительные компоненты. Один из них при результате "остановится" запускает бесконечный цикл, а второй, получив результат "не остановится", моментально останавливается. Эту новую машину назовем H+. Программу для этой машины мы можем записать на ленту в виде кода: "что будет, если дать этой машине ее собственный код?"

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

Любые выходные данные, получаемые от H, оказываются ложными. Противоречит. Единственное объяснение состоит в том, что машины H не может быть. Невозможно предсказать, какие данные точно заставят машину Тьюринга остановиться. А это значит, что математика неразрешима. Нет такого алгоритма, который всегда мог бы определить, выводится ли утверждение из аксиом. Вероятно, гипотезу о числах близнецах так и не удастся подтвердить.

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

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

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

Проблема остановки для них — это вопрос замощения поверхности. Для сложных квантовых систем, полных по Тьюрингу, проблема остановки — это вопрос спектральной щели. Игра "Жизнь" полная по Тьюрингу, ее аналог проблемы остановки. Остановится игра или нет? Есть много других примеров: продажа авиабилетов, карточная игра Magic, слайды в PowerPoint, эксcelевские таблицы. Почти все языки программирования созданы полными по Тьюрингу.

В теории нам нужен только один язык программирования, ведь с помощью одной системы, полной по Тьюрингу, можно запрограммировать что угодно. Вот, например, машина Тьюринга внутри игры "Жизнь", а так как игра "Жизнь" сама является полной по Тьюрингу, она должна уметь симулировать саму себя, и она умеет это. Игра "Жизнь" запущена внутри игры "Жизнь".

Жизнь — мечта Давида Гильберта нашла свое реальное воплощение в современных вычислительных машинах. Курт Гедель последние годы жизни страдал от психических расстройств. Он думал, что его хотят отравить, отказывался от пищи и в конечном итоге умер от голода. Гильберт же умер в сорок третьем. Его эпитафией стали слова из его же выступления: "Мы должны знать, и мы будем знать".

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

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

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

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

Переведено и озвучено студией Арт Дайдар.