# «Мы должны знать»: как дыра в логике создала современный компьютер Источник: https://www.youtube.com/watch?v=HeQX2HjkcNo Канал: Veritasium Опубликовано: 22.05.2021 --- В 1931 году математик Курт Гёдель опубликовал доказательство, которое навсегда изменило представление о границах человеческого познания. Он математически обосновал, что в любой сложной логической системе всегда будут существовать истинные утверждения, которые принципиально невозможно доказать. [15:29] Этот фундаментальный изъян логики не только поставил крест на мечтах о «совершенной математике», но и привел к созданию современных компьютеров. ## 🕹️ Непредсказуемость простых правил [[JUMP:01:03]] Математик Джон Конвей в 1970 году представил игру «Жизнь», которая наглядно демонстрирует проблему неопределенности [01:03]. Игра проходит на бесконечной сетке, где клетки могут быть «живыми» или «мертвыми». Развитие системы определяют всего два правила: * Мертвая клетка оживает, если у неё ровно три живых соседа [01:28]. * Живая клетка умирает, если у неё меньше двух или больше трёх соседей [01:28]. Несмотря на простоту, поведение системы невозможно предсказать алгоритмически. Не существует способа заранее вычислить, стабилизируется ли конкретный узор, исчезнет или будет расти бесконечно [02:34]. Эта задача относится к категории **неразрешимых проблем** (**undecidable**) [02:48]. Нельзя создать универсальный алгоритм, который даст ответ за конечное время. ## 🔢 Революция Георга Кантора и разные бесконечности [[JUMP:03:36]] В 1874 году Георг Кантор опубликовал работу по теории множеств, которая вызвала раскол в научном сообществе [03:36]. Он задался вопросом, совпадает ли размер бесконечного множества натуральных чисел (1, 2, 3...) с размером множества вещественных чисел (включая дроби и иррациональные числа вроде Пи). С помощью **диагонального метода Кантора** математик доказал, что эти бесконечности имеют разный масштаб [06:15]. Вещественных чисел между 0 и 1 принципиально больше, чем всех целых чисел до бесконечности. Это открытие шокировало современников. Анри Пуанкаре назвал теорию множеств «болезнью», а Леопольд Кронекер открыто называл Георга Кантора «шарлатаном» [07:42]. ## 🧔 Парадокс Рассела и кризис формализма [[JUMP:07:55]] К концу XIX века математики разделились на два лагеря. Интуиционисты считали математику творением человеческого разума. Формалисты под руководством Давида Гильберта верили, что науку можно поставить на абсолютно прочный логический фундамент [07:55]. Давид Гильберт стремился создать систему аксиом, которая была бы полной, непротиворечивой и разрешимой. В 1901 году Бертран Рассел обнаружил критическую уязвимость в основаниях этой системы [08:46]. Он сформулировал парадокс на примере деревенского парикмахера: * Закон гласит: парикмахер бреет только тех мужчин, которые не бреются сами [09:39]. * Должен ли парикмахер брить самого себя? [09:58] * Если он бреется сам, он нарушает правило. Если не бреется — он обязан себя брить по закону. Этот парадокс самоприменимости показал, что бесконтрольное создание множеств ведет к логическим противоречиям [10:11]. Позже Бертран Рассел и Альфред Норт Уайтхед попытались исправить ситуацию в монументальном труде **Principia Mathematica** [12:42]. На доказательство того, что 1+1=2, в этой книге ушло 762 страницы [12:54]. ## 📑 Гёдель против Гильберта: конец мечты [[JUMP:13:40]] На конференции в 1930 году Давид Гильберт провозгласил свой знаменитый лозунг: «Мы должны знать, мы будем знать» [14:39]. Однако за день до этого Курт Гёдель представил решение первой проблемы Гильберта — о полноте математики. Ответ был отрицательным [14:54]. Курт Гёдель использовал метод, названный **гёделевой нумерацией** [15:43]. Он присвоил каждому математическому символу и уравнению уникальный числовой идентификатор. С помощью сложных манипуляций с простыми числами он сконструировал утверждение, которое буквально гласило: «У этого утверждения нет доказательства» [19:46]. Логическая ловушка Гёделя: * Если это утверждение ложно, значит, у него есть доказательство. Но это создает противоречие внутри системы [20:01]. * Если утверждение истинно, значит, существуют истины, которые нельзя доказать. Система становится **неполной** [20:26]. Вторая теорема Гёделя нанесла еще более сильный удар: любая непротиворечивая система не способна доказать свою собственную непротиворечивость [21:56]. Всегда остается риск, что в будущем логика даст сбой. ## 💻 Алан Тьюринг и рождение компьютера [[JUMP:22:13]] В 1936 году Алан Тьюринг нашел ответ на третий вопрос Давида Гильберта — о разрешимости. Для этого он изобрел концепцию **машины Тьюринга** — прообраза современного программируемого компьютера [22:39]. Алан Тьюринг сосредоточился на «проблеме остановки» (**halting problem**). Он доказал, что невозможно создать алгоритм, который бы заранее предсказывал, остановится любая произвольная программа или будет работать вечно [24:16]. Поскольку проблему остановки нельзя решить, математика является **неразрешимой** [26:47]. Разработки Алана Тьюринга имели колоссальное практическое значение: 1. В годы Второй мировой войны он возглавил команду в Блетчли-Парк для взлома нацистских кодов [30:54]. 2. Его работа сократила войну, по разным оценкам, на 2–4 года [31:01]. 3. Совместно с Джоном фон Нейманом он спроектировал ENIAC — первый настоящий электронный компьютер [31:10]. ## 🌌 Тьюринговская полнота в физике и играх [[JUMP:27:20]] Концепция **тьюринговской полноты** означает, что система способна выполнить любое вычисление, на которое способна машина Тьюринга [28:36]. Это свойство обнаруживается в самых неожиданных местах: от карточной игры Magic: The Gathering до таблиц Microsoft Excel и слайдов PowerPoint [29:19]. В 2015 году математики доказали, что фундаментальные вопросы физики также могут быть неразрешимыми. Речь идет о **спектральном зазоре** (**spectral gap**) в квантовой механике — разнице в энергии между основным и первым возбужденным состоянием системы [27:37]. Невозможно создать общий алгоритм, который определил бы наличие этого зазора для любого материала [28:10]. Даже полное знание микроскопических свойств частиц не гарантирует понимания макроскопического поведения материи. Несмотря на «дыру» в фундаменте, математика не разрушилась. Поиск ответов на неразрешимые вопросы привел к трансформации теории бесконечности и созданию цифровой цивилизации [32:27].