НИКАКОЙ АЛГОРИТМ НЕ МОЖЕТ РАСПОЗНАТЬ НЕКОТОРЫЕ ЧЕТЫРЁХМЕРНЫЕ ФИГУРЫ

На некоторые вопросы не существует рецепта. Не потому, что его ещё никто не нашёл, а потому, что доказано: ни один алгоритм — никакая пошаговая процедура, сколь угодно долгая, запущенная на любом компьютере, — не может каждый раз отвечать на них правильно. Кэмерон Гордон (Cameron McA. Gordon) из Техасского университета в Остине добавляет к ним два таких вопроса о четырёхмерных фигурах.

Та же ли это фигура?

Математики называют такие фигуры 4-многообразиями: это пространства, которые вблизи везде выглядят как обычное четырёхмерное пространство. Чтобы передать их компьютеру, в статье предполагается, что они собраны из склеенных плоских кусков («кусочно-линейные», или PL, от piecewise linear), так что каждое можно описать конечным списком данных. Тогда основной вопрос звучит так: даны две такие фигуры — одинаковы ли они с точностью до непрерывной деформации?

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

Обратный отсчёт до семи

Рассуждение Маркова даже привязывает трудность к конкретным фигурам. Возьмём S² — поверхность обычного шара — и образуем произведение S² × S², четырёхмерную фигуру. Склеим k её копий («связная сумма», обозначается #k). Для некоторых k никакой алгоритм не может решить, является ли данная фигура #k(S² × S²). Для каких именно k?

Статья прослеживает этот обратный отсчёт. Группа с неразрешимой проблемой равенства слов и 12 правилами, найденная Борисовым в 1969 году, дала 14 копий. В 2022 году работа Гордона снизила это число до 12. Работа М. Танцера (M. Tancer) открыла новый путь — через классификацию четырёхмерных фигур Фридмана — и достигла 9 в «топологическом» варианте, где фигуры не обязаны быть собраны из плоских кусков. Более ранняя версия настоящей работы достигла 8. Затем Кегель, Ли и Рен (Kegel, Li, Ren) построили гораздо меньшую неразрешимую группу — 3 образующие и 9 правил, — достигнув 7 в топологическом варианте и 9 в варианте с плоскими кусками.

Гордон заставляет путь Танцера работать и для фигур, собранных из плоских кусков, и доказывает:

Не существует алгоритма, позволяющего решить, совпадает ли данное 4-многообразие, кусок за куском, со связной суммой 7 копий S² × S².

Ядро доказательства — словарь. Для каждого слова w в группе Кегеля, Ли и Рена Гордон строит четырёхмерную фигуру. Если w равно единице, последовательность допустимых преобразований правил — преобразований Эндрюса — Кёртиса (Andrews-Curtis moves), которые переписывают описание, не меняя фигуру, — показывает, что фигура — это ровно семь копий S² × S². Если нет, в фигуре есть петли, которые нельзя стянуть в точку, — чего никогда не бывает в семи копиях S² × S², — поэтому она не может быть этими семью копиями. Поэтому алгоритм, распознающий #7(S² × S²), решал бы проблему равенства слов, что невозможно.

Заузленные сферы

Второй вопрос касается узлов. Обычный узел — это окружность, завязанная в трёхмерном пространстве, и решить, можно ли развязать узел, возможно: существует алгоритм, принадлежащий Хакену. На одно измерение выше двумерная сфера может быть заузлена внутри четырёхмерного пространства. В более высоких размерностях известно, что для соответствующей задачи алгоритма не существует. Для двумерных сфер в четырёхмерной сфере S⁴ ответа никто не знает.

Гордон доказывает, что внутри #7(S² × S²) не существует алгоритма, позволяющего решить, является ли двумерная сфера — или любая поверхность, ориентируемая или нет, — незаузленной. Попутно в статье строится сфера в этой фигуре, у окружающего пространства которой группа имеет неразрешимую проблему равенства слов, а в 12 копиях S² × S² — сфера, группа которой содержит копию любой группы, которую можно описать с помощью компьютера.

Приз: ноль копий

Статья прямо формулирует цель: довести число копий до нуля. Ноль копий означает саму четырёхмерную сферу S⁴. В пяти измерениях и выше никакой алгоритм не может распознать сферу; в двух и трёх измерениях — может. Четыре измерения остаются открытым вопросом, как и вопрос о том, можно ли обнаружить заузленные сферы в S⁴. Каждая убранная копия приближает оба ответа.