ФизикаПрепринтТеория3 мин чтения

ВЕРНО, НО ДОКАЗАТЬ НЕВОЗМОЖНО

Представьте толпу соседей, у каждой пары которых свои требования. Если все требования можно выполнить одновременно, довольны все. Если два требования противоречат друг другу, кому-то придётся уступить. Физики, изучающие магниты из квантовых спинов, сталкиваются ровно с этим вопросом. У каждой пары соседних спинов есть своё энергетическое правило, и система стремится к наименьшей энергии. Когда одно состояние может удовлетворить каждую пару одновременно, модель называют свободной от фрустрации (frustration-free).

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

В работе Наото Сираиси (Naoto Shiraishi) из Токийского университета этот вопрос рассматривается для квадратной сетки спинов, где одно и то же правило повторяется для каждой пары соседей. Каждый спин может принимать d различных состояний. Ответ состоит из двух частей, которые, кажется, противоречат друг другу.

Одной решётки достаточно

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

Первая теорема устраняет эту бесконечность. Для каждого значения d существует конечный пороговый размер, один и тот же для всех возможных правил. Если модель свободна от фрустрации на сетке этого размера, она свободна от неё на всех. Значит, задача разрешима: существует алгоритм, который всегда отвечает «да» или «нет».

Ключ — классический результат алгебры, теорема Гильберта о базисе. Условие для каждого размера можно записать как систему полиномиальных уравнений, всегда с одними и теми же 2d⁴ неизвестными — элементами двух матриц правила. Теорема гарантирует, что бесконечный список таких уравнений имеет те же решения, что и некоторая его конечная часть. А поскольку сетка без фрустрации остаётся без фрустрации и на любой меньшей сетке, вырезанной из неё, хватает одного размера.

Это не тривиальный результат. Для моделей точно такого же типа было показано, что родственный вопрос — есть ли энергетическая щель над низшим состоянием — неразрешим, даже при фиксированном d.

Набор плиток, который охотится за противоречиями

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

Конструкция использует плитки Вана (Wang tiles): квадраты с цветными краями, которые укладываются без поворотов так, чтобы края соседей совпадали. Для любой компьютерной программы можно придумать конечный набор плиток, которым можно покрыть всю бесконечную плоскость, тогда и только тогда, когда программа работает вечно. Каждая плитка становится состоянием спина. Каждая запрещённая пара соседних плиток стоит одну единицу энергии. Модель свободна от фрустрации ровно тогда, когда плитки могут покрыть плоскость.

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

Модель явная, хотя и слишком сложна, чтобы её выписать. Её правила даже не вполне квантовые: все энергетические члены коммутируют, как простые классические ограничения.

Порог, который существует, но который нельзя назвать

Как задача может быть разрешимой и всё же содержать недоказуемое утверждение? Ответ — в пороге. Он конечен для каждого d, но никакой алгоритм не может вычислить его по d. Для размерности недоказуемой модели аксиомы доказывают, что конечный порог существует, — но не могут доказать, что им является какое-либо конкретное число.

К тому же порог растёт абсурдно быстро: как минимум так же быстро, как функция «усердного бобра» (busy beaver) — наибольшее число меток, которое останавливающаяся программа с заданным числом состояний может оставить на своей ленте, — а она обгоняет любую функцию, которую способен вычислить компьютер. Её значение для машин с пятью состояниями, согласно статье, было установлено лишь в 2024 году; значение для шести состояний до сих пор неизвестно.

Разрыв между «существует» и «известно»

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