Новая компьютерная программа может опровергнуть 150-летнюю математическую модель — в том случае, если вдруг перестанет работать. К счастью, такой исход крайне маловероятен.

Эта программа, получившая простое название Z, симулирует машину Тьюринга — модель вычислений, созданную знаменитым математиком Аланом Тьюрингом. В 1936 году он продемонстрировал, что действия любого компьютерного алгоритма можно воспроизвести с помощью простой машины, которая считывает и записывает нули и единицы на бесконечной ленте по определенному набору правил. Чем сложнее алгоритм, тем больше правил требуется машине для работы.

Ученые Скотт Ааронсон (Scott Aaronson) и Адам Йедидья (Adam Yedidia) из Массачусетского технологического института (MIT) создали три машины Тьюринга, исследующие глубинные математические проблемы. Одна из них включает в себя доказательство 150-летней гипотезы Римана, которая, как считается, способна объяснить некоторые закономерности простых чисел.

Различные машины Тьюринга уже давно используются для исследования подобных вопросов. Их корни лежат в нескольких философских открытиях, которые перевернули мир математики в 1930-х годах. Все началось с Курта Геделя, который продемонстрировал, что некоторые математические утверждения невозможно ни доказать, ни опровергнуть — они являются неразрешимыми.

Однако утверждение Геделя имеет специфическую лазейку. Если изменить базовые предположения, на которых построено доказательство (аксиомы), проблему можно перевести в разряд разрешимых. Однако другие проблемы при этом по-прежнему останутся неразрешимыми. Из этого следует, что аксиом, которые позволяют доказать что угодно, не существует.

Следуя доводам Геделя, Тьюринг доказал, что возможно создать машину Тьюринга, поведение которой невозможно предсказать на основе набора стандартных аксиом, известных как система Цермело — Френкеля с аксиомой выбора, или, сокращенно, ZFC. И вот теперь двум математикам из MIT удалось создать такую машину Тьюринга с 7918 состояниями, которая действительно обладает этим свойством. Она и получила имя Z. Ее примечательной особенностью является то, что если математическая модель, лежащая в ее основе, верна, то эта машина будет работать вечно.

Z спроектирована так, чтобы выполнять свои 7918 инструкций бесконечно, но если она однажды остановится, то это будет означать, что в ZFC имеются ошибки. С точки зрения математики это не является проблемой — достаточно перейти на более сильный набор аксиом, и модель снова заработает. К слову, такие аксиомы уже существуют и способны доказать поведение самой Z.

Но, помимо нее, Ааронсон и Йедидья создали еще две машины Тьюринга. Они остановятся только в том случае, если две знаменитых математических проблемы, которые уже давно считаются истинными, окажутся ложными. Это предположение Гольдбаха, утверждающее, что каждое целое четное число больше 2 представляет собой сумму двух простых чисел, и гипотеза Римана, которая утверждает, что все простые числа следуют некоторому паттерну. Второе заявление является базисом для многих частей современной теории чисел, и его опровержение станет крупным событием в мире математики.

С практической точки зрения ценность работы Ааронсона и Йедидьи заключается не в потенциальном создании вечной машины. Машины Тьюринга в целом достаточно неэффективный способ исследовать сложные математические проблемы. Вместо этого они дают другой результат — позволяют оценить их сложность. Машина Гольдбаха имеет 4888 правил, Римана — 5372, а Z — 7918, из чего следует, что проблема ZFC является самой сложной из трех.

"Умная" камера Netatmo