AI·XI Горизонты Глава 65 из 65
Белые пятна
Последняя глава — карта того, чего не знает никто. Каждое белое пятно на ней — открытый вопрос, к которому вы уже подходили вплотную: в гонке сортировок, в хеш-таблице, у бобров, в шифрах и кубитах. Рядом — ваш ящик инструментов, собранный за 65 глав, и последняя задача курса.
Горизонты
- 62 Игры
- 63 Обучение
- 64 Кванты
- 65 Белые пятна вы здесь
Опирается на: 64 · Лаборатория кубитов 57 · Письмо Гёделя
Что вы унесёте из главы
- какие вопросы computer science открыты сегодня и из каких глав курса они вырастают
- чем верхняя оценка отличается от нижней и почему зазор между ними так трудно закрыть
- как собрать небольшой работающий проект из функций, написанных в разных частях курса
В лаборатории кубитов мы упёрлись в вопрос, ответа на который нет ни в одном учебнике: умеет ли квантовый компьютер быстро хоть что-нибудь, чего быстро не умеет обычный? Такие вопросы попадались в курсе и раньше. Глава последняя, так что нарисуем карту того, чего не знает никто. Но сначала вернёмся туда, откуда начали: курс открывался числом $2^{1000}$ и пятью удивлениями. Вот число и четыре удивления из пяти снова, в одной программе; третье, дерево, рисует черепаха, и в строчку оно не помещается.
В главе 0 каждая из этих строк выглядела фокусом, теперь это упражнения. Число из 302 цифр — целое Python, у которого столько разрядов, сколько нужно (глава 28), а 302 — это $\lfloor 1000 \lg 2 \rfloor + 1$. Двадцать вопросов на миллион — двоичный поиск из главы 20 и логарифм: $2^{20} > 10^6$. Гонка — двенадцать с половиной миллионов сравнений против шестидесяти пяти тысяч, квадрат против $n \log n$, и никакой процессор этого разрыва не закроет (глава 13). Куайн — шаблон с дыркой и repr из главы 7; тем же самоотражением в главе 56 мы доказали, что Оракула не бывает.
А пятое удивление удивлением и осталось. У числа 27 — 111 шагов, у каждого числа до $2^{71}$ путь кончается единицей, но почему — не знает никто: ни мы после шестидесяти пяти глав, ни лучшие математики мира. Курс начался с белого пятна: computer science — наука, у которой край карты виден с первой страницы.
Карта неизведанного
Старые картографы оставляли неисследованные земли белыми — так было честнее, чем рисовать на них морских змеев. Ниже такая карта для computer science, нарисованная поверх этого курса. В середине — вступление, вокруг — одиннадцать частей, точки — главы. Закрашены те, что вы прочли в этом браузере. За берегом начинается туман, и в нём лежат вопросы, к которым курс вас подвёл и на которых остановился. Линии показывают, из каких глав вопрос виден.
Три вида отметок не равны друг другу. Камень — доказанный предел: здесь известно, что дальше дороги нет, и это знание такое же твёрдое, как работающий алгоритм. Проблема остановки, нижняя граница $n \log n$ для сортировки сравнениями, невозможность договориться, когда сервер может молчать сколько угодно долго, — береговые скалы. Их нашли доказательствами, и никакой новый процессор их не сдвинет. Флажок — пятно, которое закрыли. Белое пятно — место, о котором неизвестно даже, скала там или проход.
Любопытно, где пятна легли. Гуще всего они у алгоритмов и у частей IX–XI, а против машины, операционной системы и сетей туман почти пуст. Известно там, конечно, не всё, но инженерные вопросы — сколько ещё можно уменьшать транзисторы, как строить надёжное из ненадёжного — редко ставятся так, чтобы ответом была теорема. На этой карте пятна одного сорта: точные вопросы, на которые однажды ответит доказательство или алгоритм.
Береговая линия движется, и быстрее, чем кажется. Пока писался этот курс, на карте появилось несколько флажков. В июле 2024 года сообщество bbchallenge объявило, что доказало $BB(5) = 47\,176\,870$ (глава 56). В 2025 году Ран Дуань с соавторами показал, что волна Дейкстры из главы 24 не лучший возможный способ искать кратчайшие пути в ориентированном графе: их алгоритм тратит $O(m \log^{2/3} n)$ шагов и обходит «барьер сортировки», который Дейкстре навязывает куча. А одно пятно закрыл студент, который не знал, что оно пятно.
Граница знания проходит ближе, чем кажется из учебника. Учебник рассказывает о закрытых вопросах, потому что о них можно рассказать связно, а открытые лежат прямо за последним абзацем почти каждой главы. Пройдём по главным пятнам карты — от самого большого.
Самое большое пятно
Его вы знаете по главе 57. Проверить раскраску, расписание или заполненное судоку легко, найти их, похоже, трудно, — и доказать это «похоже» не удалось никому с 1971 года, когда Стивен Кук поставил вопрос в нынешнем виде. Миллион долларов Математического института Клэя на 3 октября 2026 года никто не получил. В последнем опросе Уильяма Гасарча 88 процентов специалистов ответили, что верят в $\mathrm P \ne \mathrm{NP}$, — но голосование не доказательство.
Вопрос задан обо всех алгоритмах сразу, включая те, которых ещё никто не придумал. Доказать, что задача трудна, — значит заранее исключить и Карацубу, которого Колмогоров не предвидел (глава 21), и Штрассена, о котором речь впереди, и всех, кто придёт после них. Хуже того, известны барьеры — целые семейства приёмов, про которые строго доказано, что они здесь не помогут. Диагональ, победившая Оракула в главе 56, не работает: это показали Бейкер, Гилл и Соловей в 1975 году. В 1990-х годах Александр Разборов и Стивен Рудич описали «естественные доказательства» — так были устроены почти все известные тогда нижние оценки для логических схем — и доказали, что если существуют достаточно стойкие односторонние функции, то естественным доказательством $\mathrm P \ne \mathrm{NP}$ не получить. Выходит петля: криптографы надеются, что односторонние функции есть, а их существование закрывает самый привычный путь к доказательству неравенства $\mathrm P \ne \mathrm{NP}$, без которого их не бывает.
Есть ли односторонние функции
В главе 60 мы признались, что вся криптография с открытым ключом стоит на непроверенном фундаменте. Односторонняя функция легко вычисляется и трудно обращается, причём трудно почти для каждого входа. Если такие функции есть, то $\mathrm P \ne \mathrm{NP}$: обратить функцию — значит найти вход по выходу, а проверить найденное легко. Обратное неизвестно. Может оказаться, что $\mathrm P \ne \mathrm{NP}$, но трудные случаи редки и случайный ключ почти всегда лёгок. Тогда шифров не будет, хотя главный вопрос решится «правильно».
Рассел Импальяццо в 1995 году описал пять возможных миров. В «Алгоритмике» $\mathrm P = \mathrm{NP}$ и криптографии нет. В «Эвристике» трудные задачи есть, но в среднем всё решается быстро. В «Пессиландии» трудные в среднем задачи есть, но спрятать в них секрет нельзя. В «Миникрипте» есть односторонние функции — хватит на подписи и пароли, но не на открытый ключ. В «Криптомании» есть всё, что мы делали в части X. Мы ведём себя так, будто живём в Криптомании, но в каком мире мы живём, неизвестно.
В 2020 году Яньи Лю и Рафаэль Пасс нашли связь с главой 47. Помните колмогоровскую сложность — длину самой короткой программы, печатающей строку? Если ограничить такой программе время работы, получится мера сжимаемости, которую в принципе можно вычислить. Лю и Пасс доказали: односторонние функции существуют тогда и только тогда, когда эту меру трудно вычислять в среднем. Пятно шифровальщиков и пятно архиваторов оказались одним пятном.
Пятно внутри пятна: одинаковые графы
Если $\mathrm P \ne \mathrm{NP}$, между лёгкими задачами и NP-полными обязательно есть промежуточные — это теорема Ладнера из главы 57. Кандидатов в промежуточные мало: разложение на множители, дискретный логарифм и изоморфизм графов. Даны два графа. Можно ли так переименовать вершины первого, чтобы получился второй? Сертификат — само переименование, и проверить его легко: вы сделаете это в задаче ниже. Найти его труднее. Перебор всех переименований — $n!$ вариантов, и даже для графов из главы 19 это безнадёжно.
В ноябре 2015 года Ласло Бабаи из Чикагского университета объявил алгоритм, который решает задачу за квазиполиномиальное время $2^{O((\log n)^c)}$ — медленнее любого многочлена, но несравнимо быстрее экспоненты. Харальд Хельфготт нашёл в анализе ошибку, и 4 января 2017 года Бабаи отозвал оценку. Через пять дней он объявил исправление, а Хельфготт, разобрав его, подтвердил, что оно верно, и показал, что можно взять $c = 3$. Насколько велик выигрыш? Сделайте ставку, прежде чем считать.
Граф из ста вершин. Какое из двух чисел больше: $2^{(\log_2 n)^3}$ — шаги квазиполиномиального алгоритма без постоянных множителей — или $2^n$, полный перебор всех подмножеств вершин?
При $n = 100$ показатель $(\log_2 100)^3 \approx 6{,}64^3 \approx 293$, а у экспоненты — всего 100. Квазиполином становится выгоднее экспоненты только на больших графах: асимптотика говорит о росте, а не о том, кто лучше на конкретном входе. Ячейка ниже сравнивает порядки — сколько цифр в числе шагов — для разных $n$.
Таблица отрезвляет. На тысяче вершин квазиполином всё ещё наравне с полным перебором. Прежний рекорд — $2^{O(\sqrt{n \log n})}$, Бабаи и Юджин Люкс, 1983 год — он обгоняет примерно с шести миллионов вершин, и то если забыть о постоянных множителях. Быстрее на деле он ничего не считает: графы сравнивают программами, которые с 1970-х годов хорошо работают на случайных графах, хотя в худшем случае тратят экспоненту. Зато он меняет карту. Если бы изоморфизм графов был NP-полон, то алгоритм Бабаи решал бы за квазиполиномиальное время любую задачу из NP, а в это почти никто не верит. Значит, изоморфизм, скорее всего, лежит в промежутке — в стране, существование которой зависит от главного пятна.
Графы заданы, как в главе 19: словарь «вершина → список соседей», граф неориентированный (каждое ребро записано у обоих концов), одинокие вершины — ключи с пустым списком. Переименование f — словарь «вершина первого графа → вершина второго». Напишите is_isomorphism(g1, g2, f): True, если f — изоморфизм, то есть разным вершинам g1 даёт разные вершины g2, задано на всех вершинах g1, задевает все вершины g2 и переводит соседей ровно в соседей. Например, для «уголков» g1 = {'a': ['b', 'c'], 'b': ['a'], 'c': ['a']} и g2 = {1: [3], 2: [3], 3: [1, 2]} переименование {'a': 3, 'b': 1, 'c': 2} подходит, а {'a': 1, 'b': 3, 'c': 2} — нет. В тестах есть звезда на сто тысяч лучей и кольцо на двести тысяч вершин.
Заготовка проверяет только половину сертификата: что каждое ребро первого графа переходит в ребро второго. А если f склеила две вершины в одну? А если во втором графе есть лишние рёбра или лишние вершины? Сертификат должен доказывать равенство графов, а не вложение одного в другой.
Взаимную однозначность проверяют множества из главы 8: ключи f — это ровно вершины g1, значения все разные, и их множество — ровно вершины g2. Тогда для каждой вершины v достаточно сравнить два множества: образы соседей v и соседей f[v].
У центра звезды сто тысяч соседей. Проверка x in список перебирает список, и сто тысяч таких проверок — десять миллиардов сравнений. Множество отвечает на in за одно действие (глава 16).
Проверка линейна: каждое ребро трогаем по разу с каждого конца. Так и выглядит «проверить легко» из главы 57: сертификат изоморфизма проверяется за $O(n + m)$, а лучший известный способ его найти — квазиполиномиальный. Сравнение множеств соседей заодно ловит лишние рёбра второго графа: если у f[v] есть сосед, который не образ соседа v, множества не совпадут.
Пятно, которое сжимается
Большинство пятен на карте неподвижны десятилетиями. Это — редкое исключение: его край можно нарисовать на графике, и он ползёт.
Восемь против семи кажется мелочью, пока не вспомнишь главу 21. Матрицу $n \times n$ режут на четыре блока, и формулы Штрассена работают для блоков так же, как для чисел. Получается рекурсия $T(n) = 7\,T(n/2) + O(n^2)$, и по основной теореме время растёт как $n^{\log_2 7} \approx n^{2{,}807}$. Проверим формулы на тысяче случайных пар и посчитаем выигрыш.
Для матриц $8192 \times 8192$ разница уже впятеро с лишним. Тысяча совпадений — свидетельство, но ещё не доказательство. А в задаче ниже вы увидите, что для формул такого вида шестнадцать удачно выбранных проверок уже доказательство.
Штрассен открыл гонку, как Карацуба до него. Число $\omega$ такое, что матрицы $n \times n$ можно перемножить за $O(n^{\omega + \varepsilon})$ действий при любом $\varepsilon > 0$, а с показателем меньше $\omega$ — нельзя, называют показателем умножения матриц. Школьное правило даёт $\omega \le 3$, Штрассен — $\omega < 2{,}81$. Снизу видно только $\omega \ge 2$: в ответе $n^2$ чисел, и каждое надо хотя бы записать. Всё, что между, — белое пятно, и его правый край полвека двигают влево.
Самая крутая часть графика — 1970-е и начало 1980-х: Пан, Бини с соавторами, Шёнхаге, Копперсмит и Виноград сбросили почти треть единицы. В 1990 году Копперсмит и Виноград дошли до $2{,}3755$, и на двадцать лет график замер. С 2010 года оценку снова двигают, но уже в третьем–шестом знаке после запятой: Эндрю Стозерс, Вирджиния Василевская-Уильямс, Франсуа Ле Галль и другие уточняют один и тот же «лазерный метод». Продлите тренд разных лет: на вопрос «когда же двойка» он отвечает очень по-разному. Прямая через 1969–1990 годы обещала двойку ещё до 2010-го, прямая через последние полтора десятилетия — через тысячи лет. Прямая знает только скорость прошлых рекордов, а новый метод может изменить её в любую сторону.
Рекорды последних десятилетий на практике не применяют. Постоянные множители в них так велики, что выигрыш наступил бы на матрицах, которые не поместятся ни в какую память. Такие алгоритмы в шутку называют галактическими: они выигрывают на входах астрономического размера. Библиотеки, которые перемножают матрицы для нейросетей, считают по школьному правилу, только очень аккуратно с кэшем из главы 34 и параллельно, а штрассеновские схемы применяют от случая к случаю. Зато каждый такой рекорд сдвигает край пятна.
В последние годы к поиску подключились машины. В 2022 году система AlphaTensor из DeepMind нашла схему для матриц $4 \times 4$ из 47 умножений вместо 49 у дважды применённого Штрассена — правда, только для арифметики по модулю 2. А 17 августа 2026 года вышел препринт десяти авторов — семи исследователей Google DeepMind и трёх авторов прежних рекордов: Джоша Алмана, Вирджинии Василевской-Уильямс и Жэньфэя Чжоу. Оптимизационную задачу внутри лазерного метода они решали новыми средствами, в том числе агентом AlphaEvolve, который пишет и улучшает программы с помощью языковой модели. Новая оценка — $\omega < 2{,}371177$, предыдущая была $2{,}371339$. На 3 октября 2026 года это препринт в arXiv, без отметки о публикации в журнале или на конференции. Общепринятой оценка станет, когда её проверят люди или программы; то, что её помог найти ИИ, тут ничего не решает.
Схема умножения матриц $2 \times 2$ из $r$ умножений записана словарём. scheme["a"][k] — четыре коэффициента, с которыми элементы $a_{11}, a_{12}, a_{21}, a_{22}$ матрицы $A$ входят в левый множитель $k$-го произведения; scheme["b"][k] — то же для $B$ и правого множителя; scheme["c"] — четыре строки длины $r$: с какими весами произведения $m_1, \ldots, m_r$ входят в $c_{11}, c_{12}, c_{21}, c_{22}$. Схема Штрассена в такой записи — в заготовке. Напишите multiply(scheme, A, B) — произведение по схеме (матрицы — списки строк, числа целые или дроби Fraction) и is_correct(scheme) — верна ли схема для любых матриц. Тесты подсовывают верные схемы и схемы с одной ошибкой в знаке, с лишним слагаемым, «экономные» схемы из шести умножений.
multiply: вытяните элементы матриц в списки [a11, a12, a21, a22] и [b11, b12, b21, b22]. Левый множитель $k$-го произведения — сумма попарных произведений коэффициентов scheme["a"][k] и этого списка (zip из главы 10), правый — то же для b. Каждый элемент ответа — такая же взвешенная сумма уже готовых произведений.
Одна пара матриц ничего не доказывает: ошибка в схеме может «спрятаться» на удачных числах. Можно проверять на сотне случайных пар с большими числами — неверная схема почти наверняка где-нибудь промахнётся, это метод Монте-Карло из главы 26. Но есть способ без «почти».
Каждый элемент ответа — сумма слагаемых вида «коэффициент × $a_{pq}$ × $b_{rs}$». Чтобы узнать коэффициент при $a_{pq} b_{rs}$, подставьте матрицу $A$ с единицей на месте $pq$ и нулями в остальных клетках и такую же $B$ с единицей на месте $rs$. Шестнадцать таких пар узнают все коэффициенты схемы.
Шестнадцати проверок достаточно: каждый элемент результата схемы — сумма $\sum c_{pqrs}\, a_{pq} b_{rs}$ по шестнадцати парам, у правильного произведения — тоже, только с коэффициентами 0 и 1. Две такие суммы равны при любых матрицах тогда и только тогда, когда совпадают все шестнадцать коэффициентов, а матрицы с одной единицей вытаскивают их по одному. Это свойство билинейности, о нём — «Царица наук». Случайная проверка тоже работает: ненулевой многочлен второй степени редко обращается в ноль на случайных больших числах, — но шестнадцать единичных пар отвечают точно. Так стоит проверять любую схему, кто бы её ни нашёл: человек, перебор или нейросеть.
У $\omega$ есть младший брат из главы 21 — умножение чисел. Там гонка, начатая Карацубой, дошла в 2019 году до $O(n \log n)$: это сделали Дэвид Харви и Йорис ван дер Хувен, статья вышла в Annals of Mathematics в 2021-м. Шёнхаге и Штрассен, авторы рекорда 1971 года, предполагали, что лучше $n \log n$ нельзя. Верхняя оценка до этой догадки дошла, а доказательства нижней нет, и зазор шириной в один логарифм так и не закрыт.
Зазоры
У пятна вокруг $\omega$ два берега. Правый — верхняя оценка: $\omega < 2{,}371177$, потому что вот алгоритм. Левый — нижняя: $\omega \ge 2$, потому что вот доказательство, что быстрее нельзя никаким алгоритмом. Чтобы сдвинуть правый берег, достаточно придумать один способ. Чтобы сдвинуть левый, нужно рассуждение обо всех способах сразу, включая не придуманные. Поэтому верхние оценки движутся, а нижние десятилетиями стоят на месте, и чаще всего это тривиальное «надо хотя бы прочитать вход».
Ниже — зазоры нескольких задач курса. Серая часть шкалы — то, что доказуемо невозможно, цветная — то, что мы умеем, белая между ними — пятно. Нажмите на строку, чтобы увидеть, как двигался правый берег.
Единственная строка без белого — сортировка сравнениями. В главе 20 мы доказали деревом решений, что любая сортировка, которая только сравнивает, делает не меньше $\log_2 n! \approx n \log_2 n$ сравнений, а слияние столько и делает. Это редкое счастье: задача, про которую известно всё. Остальные строки — норма. Для коммивояжёра с неравенством треугольника из главы 58 известный быстрый алгоритм даёт маршрут длиннее оптимального не больше чем в $1{,}5 - 10^{-34}$ раза (в среднем по своим случайным выборам), а доказано только, что гарантии лучше $123/122 \approx 1{,}008$ не бывает, если $\mathrm P \ne \mathrm{NP}$. Между ними почти половина оптимума неизвестности. Для кратчайших путей правый берег сдвинулся в 2025 году, а левый так и стоит на $m$, числе рёбер: каждое ребро надо хотя бы посмотреть.
Край, за которым не видно
Есть пятна другого рода. Про P и NP хотя бы понятно, как выглядел бы ответ: алгоритм или доказательство. Про некоторые вопросы неизвестно даже, можно ли на них ответить в принципе.
Начнём с бобров. После победы над пятью состояниями в 2024 году (глава 56) участники bbchallenge взялись за шесть. Лучшая известная машина-чемпион с шестью состояниями найдена участником mxdys в июне 2025 года: она останавливается, но число её шагов больше $2 \uparrow\uparrow\uparrow 5$ — башни из двоек, высота которой равна башне из двоек высотой 65 536. Это нижняя оценка $BB(6)$. Верхней не известно никакой, а по теореме Радо никакая вычислимая функция не ограничивает $BB(n)$ сверху сразу для всех $n$. Чтобы найти $BB(6)$, надо решить про каждую машину с шестью состояниями, остановится ли она. На конец сентября 2026 года в списке нерешённых оставалось 815 машин — если считать одной машиной равносильные, например отличающиеся только именами состояний. Среди них «Антигидра» из той же главы: она остановится, только если одна последовательность в духе Коллатца поведёт себя так, как от неё никто не ждёт. Участники проекта формулируют вывод прямо: чтобы найти $BB(6)$, придётся решить задачу в духе Коллатца.
Сама гипотеза Коллатца на 3 октября 2026 года открыта. Компьютеры проверили все числа до $2^{71}$ — это сделал Давид Барина, результат 2025 года. Самое сильное доказанное утверждение получил в 2019 году Теренс Тао: почти у всех чисел путь опускается сколь угодно низко — ниже любой, сколь угодно медленно растущей функции от начального числа. «Почти все» здесь — в точном смысле плотности, и исключения не запрещены. Чтобы почувствовать, что значит $2^{71}$, проверим на сервере столько чисел, сколько успеем за секунду. Есть удобная хитрость: если все числа меньше $n$ уже проверены, достаточно убедиться, что путь числа $n$ опустится ниже $n$, — дальше он идёт по уже проверенному.
Наш сервер проверяет миллионы чисел в секунду и всё равно потратил бы на путь до $2^{71}$ десятки миллионов лет. Рекорд держится на параллельных вычислениях, на программах, написанных на языках поближе к железу из части IV, и на хитростях, которые отбрасывают большинство чисел без счёта. К доказательству всё это не приближает ни на шаг: сколько чисел ни проверь, контрпример может лежать дальше.
Есть основания подозревать, что некоторые такие пятна закрыть нельзя вовсе. В 1972 году Джон Конвей доказал, что для обобщённых правил в духе Коллатца вопрос «дойдёт ли до единицы» неразрешим (глава 56). А машина с 745 состояниями останавливается тогда и только тогда, когда противоречива ZFC — аксиоматика, на которой стоит почти вся математика. Значит, если ZFC непротиворечива, точное значение $BB(745)$ её средствами не установить: это теорема Гёделя из Кёнигсберга в одежде бобра. Где-то между шестью и семьюстами сорока пятью состояниями проходит граница, за которой «белое пятно» значит «здесь нельзя знать». Где именно она проходит, тоже неизвестно.
На горизонте
Последние три пятна — на краю части XI, и они ближе всего к новостям, поэтому говорить о них стоит особенно трезво.
Кубиты. Это пятно вы только что разглядывали вблизи в главе 64, поэтому коротко. Неизвестно, шире ли BQP, чем P, — и доказательство заодно разделило бы P и PSPACE из главы 57, а это пятно того же калибра, что главное. Неизвестно, как BQP соотносится с NP. И с другой стороны неизвестно, не найдётся ли быстрый способ разлагать числа на множители вовсе без кубитов: тогда RSA падёт раньше, чем построят большой квантовый компьютер, а алгоритм Шора потеряет главный козырь. Пятно двустороннее. Каждый новый опыт с кубитами может оказаться и прорывом, и задачей, которую обычные компьютеры ещё не научились решать быстро, — так уже вышло с опытом 2019 года (глава 64, «Как читать новости»).
Шахматы. Шашки решены в 2007 году — ничья, «Четыре в ряд» — в 1988-м, победа первого (глава 62). Чем кончится идеальная партия в шахматы, неизвестно. Летом 2012 года Владимир Махнычев и Виктор Захаров на суперкомпьютере МГУ «Ломоносов» досчитали почти все позиции с семью фигурами — около 140 терабайт таблиц, а к 2018 году семь фигур досчитали полностью. Позиции с восемью фигурами на 2026 год досчитаны лишь частично. В начальной позиции фигур тридцать две.
Машины, которые учатся. На одиннадцатый большой вопрос глава 63 ответила «да, но»: сеть находит правило, которого не писал программист, и ошибается там, где новое не похоже на виденное. Что за этим «но», — самое людное пятно на карте. Нет общепринятой теории, которая объясняла бы, почему огромные сети, способные выучить обучающую выборку наизусть, всё-таки обобщают на новое (экзамен из главы 63). Неизвестно, где кончаются возможности языковых моделей, которые предсказывают следующее слово, и что из их поведения можно назвать рассуждением. И уже сейчас эти машины работают на краю нашей карты: оценка $\omega$ 2026 года из раздела выше получена с участием агента, написанного вокруг языковой модели. Но роль у агента — предлагать, а принимает предложение доказательство, которое проверяет человек или программа. Как устроены такие модели изнутри, можно разобрать своими руками в курсе «Росток»: там вы обучите языковую модель с нуля.
Ящик инструментов
Теперь карта изведанного. Белые пятна видны вам потому, что вы дошли до их края, и дошли не с пустыми руками. За 65 глав вы написали интерпретатор Лиспа, компилятор для машины, которую сами собрали из вентилей, поисковик по учебникам этого сайта, SAT-решатель, обмен ключами и бота для «Четырёх в ряд». Если вы решали задачи в этом браузере, ниже лежит всё, что вы в них написали.
Задач в курсе больше двухсот сорока, а идей под ними гораздо меньше, и они возвращаются. Разделить пополам: двадцать вопросов из главы 0, двоичный поиск, сортировка слиянием, Карацуба, Штрассен, B-дерево в базе данных, поиск коммита с ошибкой в git. Запомнить, чтобы не считать: динамическое программирование, кэш процессора, индекс базы данных. Сделать работу заранее: хеш ключа, обратный индекс поисковика, ориентиры навигатора. Спрятать сложность под слоем: функция, процесс, протокол, виртуальная память. Свести одну задачу к другой: раскраска в формулу, остановка в «Привет, мир», любая задача NP в SAT. Бросить монетку: Монте-Карло, соль хеш-таблицы, Миллер — Рабин, поиск по дереву игры. Держать инвариант: границы двоичного поиска, кворум Паксоса, корректность жадного шага. Посмотреть на себя: куайн, упрямец, компилятор, который компилирует себя. Когда в следующий раз задача не поддастся, переберите этот список — скорее всего, ключ в нём.
И одиннадцать вопросов из главы 0 получили ответы. Программа печатает себя (глава 7). Одну программу быстрее другой делает функция роста (13). Навигатор ведёт волну Дейкстры по графу с кучей (24). Компьютер собирается из выключателей (32). Сотня программ уживается на двух ядрах через ядро ОС, планировщик и блокировки (39). Миллиарды машин работают без главного, потому что ни один слой сети не держится на одной машине, а копии договариваются большинством (44). Поисковик ищет заранее (48). Программа понимает программу по дереву (52). Задачи, которые не решит никакой компьютер, есть (56). О секрете договариваются через одностороннюю функцию (60). Машина учится тому, чему её не учили, — в границах данных (63). На два из этих ответов карта неизведанного бросает тень. Ответ десятого держится на односторонних функциях, существование которых не доказано, а ответ одиннадцатого — на обобщении, которое никто толком не объяснил.
Последняя задача: путеводитель
Последняя задача курса — маленький проект, в котором сходятся несколько приёмов. Вы соберёте путеводитель по этому самому курсу: человек вводит, что хочет понять, — «хеш-таблица», «белые пятна», хоть «машина тюринга» с ошибкой, — и программа находит главу и составляет маршрут: какие главы прочесть и в каком порядке. Данные у вас есть, это граф курса из главы 19.
Путеводитель сшивает умения из разных частей курса. Чтобы понять запрос, нужны строки и нормализация из главы 7 и главы 48. Чтобы простить опечатку — расстояние Дамерау из главы 22. Чтобы собрать все нужные главы — обход графа без рекурсии, потому что цепочка зависимостей бывает длиннее стека (глава 9). Чтобы расставить их по порядку — топологическая сортировка из главы 19 с кучей из главы 18. Чтобы не уснуть на большом курсе — оценка сложности из главы 13. Чтобы внятно отказать на круге или незнакомом слове — исключения из главы 11. Если вы решали задачи «Порядок чтения» и «Поправка Дамерау», ваши функции лежат в ящике выше — берите их.
Курс — список глав в порядке номеров; глава — словарь с ключами "slug", "title" и "prereq" (слаги глав, которые надо прочесть раньше; лишние ключи не мешают). Напишите две функции.
find(course, query) — слаг главы по запросу человека или None. Если запрос без пробелов по краям и в нижнем регистре совпадает со слагом какой-нибудь главы, это она. Иначе запрос и названия режутся на слова: нижний регистр, ё → е, слово — непрерывный кусок русских и латинских букв и цифр ("Хеш-таблица: атака" → хеш, таблица, атака). Слово запроса подходит к слову названия, если они равны; или одно начинается с другого, а короткое не короче четырёх букв (дерев и деревьев); или оба не короче пяти букв и расстояние Дамерау между ними не больше 1 (таблца и таблица). Очки главы — сколько слов запроса подходят хотя бы к одному слову её названия. Побеждает глава с наибольшими очками, при равенстве — та, что раньше в курсе; если очков нет ни у кого — None.
plan(course, query) — маршрут чтения: список слагов. Главу находит find; не нашлась — ValueError. В маршрут входят она и все главы, от которых она зависит прямо или через другие, и больше ничего. Каждая глава идёт после всех своих пререквизитов; если готовы сразу несколько, раньше идёт та, что раньше в курсе. Если среди нужных глав пререквизиты замыкаются в круг — ValueError. Тесты проверяют путеводитель целиком: на маленьких курсах, на реальном графе этого курса и на курсе из тридцати тысяч глав.
Разбейте find на маленькие функции, как в главе 5: similar(q, w) — подходит ли одно слово к другому по трём правилам; очки главы — sum по словам запроса от any по словам названия. Проход по курсу по порядку со строгим «больше» сам решит ничьи в пользу ранней главы. Дамерау для слов, длины которых различаются больше чем на единицу, можно не считать: такое расстояние заведомо больше 1.
В plan сначала соберите множество нужных глав: от цели по стрелкам «прочтите сначала», как волна из главы 19. Рекурсия здесь опасна: на цепочке из тридцати тысяч глав она упрётся в предел глубины из главы 9. Возьмите явный стек или очередь.
Порядок — алгоритм Кана из главы 19, только на нужных главах: у каждой счётчик непрочитанных пререквизитов, готовые — в куче, где ключ — номер главы в курсе. Перебирать все главы в поисках готовой на каждом шаге нельзя: на тридцати тысячах это девятьсот миллионов проверок. Если куча опустела, а выписаны не все нужные главы, — значит, где-то круг.
Семьдесят строк, и почти каждая пришла из своей главы: регулярное выражение и нормализация — из глав 7, 48 и 54, Дамерау — из 22, обход — из 19, куча — из 18, исключения — из 11, а сама мысль, что перебор готовых глав на каждом шаге — это квадрат, который на тридцати тысячах не дождётся ответа, — из 13. Новая задача редко требует нового алгоритма; чаще нужно узнать в ней старые и правильно их соединить. Для нашего курса маршрут к белым пятнам проходит почти через половину глав — проверьте, через сколько именно.
Куда дальше
У этой главы нет следующей. Шестьдесят пять глав назад курс обещал спуститься от строчки на Python к выключателям и подняться обратно, а в конце спросить, чего не сможет никакой компьютер. Всё это пройдено, и вместо стены, которой обычно кончается глава, здесь развилка.
Если хочется глубже в то, что уже пройдено, — на портале computer science готовятся следующие курсы: каталог алгоритмов с визуализациями и кодом, курс о системах и сетях глубже базового, компьютерная графика от пикселя до трассировки лучей. Пока они в работе, все задачи этого курса собраны на странице практики, а все термины — в словаре. Если хочется понять математику, на которой стоял курс, — графы, вероятности, остатки, линейную алгебру, — для этого есть «Царица наук», и её последняя глава, «Передний край», — такая же карта неизведанного, только нарисованная математиками: там те же Коллатц и P против NP, а рядом задачи тысячелетия. Если хочется заглянуть внутрь машин, которые учатся, — в курсе «Росток» вы обучите собственную языковую модель с нуля и поговорите с ней в браузере.
Белые пятна закрывают не только гении: $BB(5)$ нашли любители и профессионалы, которые собрались вокруг одного сайта, гипотезу Яо опроверг студент, не знавший, что опровергает, а проект bbchallenge открыт для всех и сейчас разбирает машины с шестью состояниями. Чтобы присоединиться, хватит того, что у вас уже есть: вы умеете написать программу, оценить её время, проверить чужое утверждение и не поверить красивой экстраполяции.
Курс начался словами «начнём сразу с кода». Закончим тоже кодом. Программа ниже берёт случайное число около $10^{30}$ — в сотни миллионов раз больше $2^{71}$ — и ведёт его по правилу Коллатца. Числа, которое выпадет вам, почти наверняка не проверял никто и никогда.
Дошло. Ещё одна точка на краю карты, и опять ничего не доказано. На этом курс кончается.