Карта → событие
П. С. Новиков: проблема тождества слов неразрешима
Задача, которая выглядит простой
Группу удобно задавать образующими и соотношениями. Пишем список букв и список равенств, которым они подчиняются, — всё остальное считается следствием. Например,
$$\left\langle a,b \;\middle|\; a^{2}=1,\ b^{3}=1,\ (ab)^{2}=1 \right\rangle$$
— это группа симметрий равностороннего треугольника, шесть элементов.
Слово — это любая строчка из образующих и обратных к ним: $abba^{-1}b$. Два слова задают один и тот же элемент группы, если одно можно превратить в другое, применяя соотношения.
Проблема тождества слов. Существует ли алгоритм, который по конечному заданию группы и двум словам определяет, равны ли они?
Задачу поставил Макс Дэн в 1911 году — вместе с двумя родственными: проблемой сопряжённости и проблемой изоморфизма. Он же решил её для фундаментальных групп замкнутых поверхностей рода $\geqslant2$ и придумал для этого алгоритм, который до сих пор носит его имя.
Вопрос выглядит технической трудностью. Соотношений конечное число, слова конечны, преобразования механические — кажется, нужно просто быть достаточно изобретательным.
Ловушка в том, что цепочка преобразований может сначала удлинять слово. Чтобы доказать равенство, иногда приходится пройти через слова во много раз длиннее исходных, и заранее неизвестно, насколько длиннее. Поэтому перебор не заканчивается: если слова равны, мы это рано или поздно обнаружим, а если не равны — будем искать вечно. Полуалгоритм есть; алгоритма нет.
Ответ
П. С. Новиков. Об алгоритмической неразрешимости проблемы тождества слов в теории групп. Труды Математического института имени В. А. Стеклова, т. 44 (1955), с. 3–143.
Сто сорок страниц — целый том, посвящённый одной теореме.
Теорема. Существует конечно определённая группа, для которой проблема тождества слов алгоритмически неразрешима.
То есть можно выписать конкретную группу — конечное число образующих, конечное число соотношений, всё помещается на страницу — про которую никакая программа никогда не сможет отвечать на вопрос «равны ли эти два слова».
Независимо и другим способом ту же теорему доказал американец Уильям Бун; его работа публиковалась частями с 1954 по 1957 год. Результат принято называть теоремой Новикова — Буна. Новикову за неё присудили Ленинскую премию 1957 года.
Как такое вообще возможно
Идея, если убрать технику, состоит в одной фразе: внутрь группы можно спрятать машину Тьюринга.
Строится группа, в которой некоторые слова кодируют состояния вычислительного устройства, а соотношения — его такты работы. Тогда вопрос «равно ли слово $w$ пустому слову» превращается в вопрос «останавливается ли машина на данном входе». Проблема остановки неразрешима (ТьюрингАлан ТьюрингОпределил, что значит «вычислить», за десять лет до появления компьютеров, взломал «Энигму» и был осуждён за то, кем он был., 1936) — значит, неразрешима и проблема тождества.
Половина работы — техническая: нужно, чтобы группа не «схлопнулась», то есть чтобы никакие посторонние следствия соотношений не разрушили кодировку. Именно на это уходят сто сорок страниц.
Дорога к этому строилась десять лет. В 1947 году А. А. МарковАндрей Андреевич МарковПридумал цепи зависимых событий, чтобы выиграть спор о том, обязательна ли независимость для закона больших чисел, — и проверил их на буквах «Евгения Онегина». (сын того самого Маркова из линии вероятностей) и, независимо, Эмиль Пост доказали неразрешимость проблемы тождества для полугрупп — там всё существенно проще, потому что нет обратных элементов и слово нельзя укоротить обратно. Переход от полугрупп к группам оказался не техническим усилением, а отдельной большой задачей.
Позже Грэм Хигман (1961) нашёл элегантное объяснение всему явлению: конечно порождённая группа вкладывается в конечно определённую тогда и только тогда, когда её множество соотношений перечислимо. Иначе говоря, конечно определённые группы способны вместить любую перечислимую конструкцию — включая любую вычислительную. Неудивительно, что вместе с этой способностью они унаследовали и неразрешимость.
Что это значит для алгебры
До 1955 года неразрешимость была явлением из логики. ГёдельКурт ГёдельДоказал, что в любой достаточно богатой формальной системе есть истинные утверждения, которые она не может доказать, — и тем закрыл программу Гильберта в двадцать пять лет., Тьюринг, ЧёрчАлонзо ЧёрчОтветил Гильберту «нет» за семь месяцев до Тьюринга — и сделал это на языке, где нет ни чисел, ни машин, а есть только функции и подстановка; из этого языка выросло функциональное программирование. говорили о формальных системах, об арифметике, о самих алгоритмах — то есть о предметах, которые сами про вычисления и рассуждения. Обычная математика чувствовала себя в стороне: считалось, что это болезнь оснований, а не рабочих областей.
Новиков перенёс её в центр обычной алгебры. Группа, заданная образующими и соотношениями, — это не искусственная конструкция логика, а способ, которым топологи задают фундаментальные группы, а комбинаторные алгебраисты — практически всё.
Следствия оказались обширными: теорема Адяна — Рабина (1955–1958) утверждает, что неразрешимо почти любое разумное свойство конечно определённых групп — быть тривиальной, конечной, абелевой, свободной. Не «трудно проверить», а невозможно.
И дальше по цепочке: раз фундаментальная группа задаётся образующими и соотношениями, а по конечному клеточному комплексу её можно выписать механически, то неразрешима и проблема гомеоморфности многообразий размерности $\geqslant4$ (Марков-младший, 1958). Топология тоже не оказалась в стороне.
Общая мораль такая. Двадцатый век дважды удивил математику. Сначала ГильбертДавид ГильбертЧеловек, сделавший Гёттинген столицей математики и задавший ей повестку на весь XX век — двадцатью тремя проблемами и одной программой, которую сам же и не смог спасти. надеялся, что всякая корректно поставленная задача имеет решение («мы должны знать — мы будем знать»), и Гёдель показал, что это не так для арифметики. Потом оставалась надежда, что это касается только оснований. Новиков показал, что не только: неразрешимость живёт в самой обыкновенной алгебре, среди объектов, которые изучают не ради философии, а ради дела.
Мост
Точка стоит на двух линиях, и в обеих она — середина одного и того же моста.
$$\text{Тьюринг (1936)} \longrightarrow \text{Новиков (1955)} \longrightarrow \text{Матиясевич (1970)}$$
Тьюринг определил, что такое алгоритм, и предъявил задачу без алгоритма — про сами машины. Новиков перенёс неразрешимость в алгебру. Матиясевич — в теорию чисел: десятая проблема Гильберта, требовавшая алгоритма для диофантовых уравнений, ответа не имеет.
Три шага, тридцать четыре года, и каждый следующий переносит неразрешимость из более искусственной области в более естественную. Последний шаг самый неприятный: диофантовы уравнения — это уже совсем не логика, это Диофант.
Люди
Пётр Сергеевич Новиков (1901–1975) — из лузинской школы; начинал в дескриптивной теории множеств, где сделал первоклассные вещи (теоремы об отделимости, о единственности для тригонометрических рядов), и лишь потом перешёл в математическую логику и алгебру, где основал советскую школу конструктивной логики.
Через тринадцать лет после проблемы тождества он вернулся к неразрешимости с другой стороны: теорема Новикова — Адяна (1968) даёт отрицательный ответ на ограниченную проблему Бернсайда — существует бесконечная группа с конечным числом образующих, в которой $x^{n}=1$ для всех элементов (при нечётных $n\geqslant4381$). Обратите внимание на соседство: общую проблему Бернсайда четырьмя годами раньше закрыл Голод, и обе точки стоят на этой линии в шести годах друг от друга.
Семья: жена — Людмила Всеволодовна Келдыш, крупный тополог (и сестра Мстислава Келдыша); сын — Сергей Петрович Новиков, филдсовский лауреат 1970 года за топологическую инвариантность классов ПонтрягинаЛев Семёнович ПонтрягинОслеп в тринадцать лет и всё считал в уме; построил двойственность топологических групп, характеристические классы и принцип максимума — три вещи из разных наук, каждая из которых пережила автора.. Двух Новиковых на карте легко перепутать; здесь — отец.
Следующая точка: конечные группы получают наконец систематическое устройство.