Все свободны

Математическую «проблему тысячелетия» решат вечно работающие машины

Математики решили доверить доказательство важнейших гипотез точной науки вечно работающим машинам. Среди таких задач — одна из «проблем тысячелетия». Если устройство прекратит работу не по физической причине (например, из-за уничтожения компьютера), научные результаты, сформулированные за последние 150 лет развития математики, потребуют пересмотра. «Лента.ру» вместе с New Scientist разбирается в исследованиях ученых.

Математики полагают, что, скорее всего, гипотезы, которые доверили проверять машинам, окажутся верными. Каждое из устройств представляет собой имитацию машины Алана Тьюринга. В простейшем случае она считывает и перезаписывает элементы 0 и 1 на бесконечно длинной (в обе стороны) ленте, следуя специальным инструкциям (состояниям). Машина Тьюринга представляет собой простейшую физическую реализацию любого компьютерного алгоритма. Чем он сложнее, тем больше требуется состояний машины.

Все физические устройства, претендующие на то, чтобы называться машиной Тьюринга, представляют собой ее имитацию. Это связано с тем, что память компьютера ограничена, а лента в машине Тьюринга — нет (в дальнейшем мы не различаем идеальную и физическую машины Тьюринга). Между тем все же возможно так подобрать алгоритм (и число состояний), чтобы соответствующая машина Тьюринга проверила ряд важных математических гипотез. Эта идея для математиков не нова.

В 1930 году Курт Гедель доказал две теоремы о неполноте. Согласно первой (для формальной арифметики) в аксиоматической системе всегда существуют некоторые утверждения, которые нельзя доказать. Преодолеть эту трудность можно, изменив саму систему аксиом. Но в новой системе аксиом возникнут новые неразрешимые затруднения: доказать нечто, не выйдя за саму систему аксиом, оказывается невозможным. Согласно второй теореме, недоказуема непротиворечивость не требующей новых аксиом системы.

В течение последних ста лет (сроки зависят от начала отсчета, и не все математики с ними согласны) разрабатывается теория ZFC (Zermelo-Fraenkel set theory with the axiom of choice) — так называемая система Цермело-Френкеля с аксиомой выбора. Из нее выводятся все утверждения современной теории множеств. В теории ZFC до сих пор не обнаружили противоречий (то есть ее аксиом пока хватает для доказательств всех утверждений).

В то же время Тьюринг показал, что существуют машины, чье поведение не предсказывается теорией ZFC, — то есть устройства, которые не описываются теоремами Геделя. До сих пор ученые не знали, насколько сложными могут быть такие машины. И только недавно математики-программисты Скотт Аронсон и Адам Едиди из Массачусетского технологического института (США) предложили три устройства Тьюринга, позволяющие проверить важнейшие математические утверждения 150-летней давности: непротиворечивость теории ZFC, гипотезу Римана и проблему Гольдбаха (последней, вообще говоря, более 270 лет).

Алан Тьюринг

Фото: wikipedia.org

Гипотеза Римана утверждает, что все нетривиальные нули дзета-функции являются комплексными числами, расположенными на прямой Re s = 0,5. Тривиальные нули дзета-функции известны и равняются отрицательным четным целым числам s = – 2, – 4, – 6 и так далее. Проблема Гольдбаха сводится к доказательству утверждения, что любое четное число, начиная с 4, представимо в виде суммы двух простых чисел. Гипотеза Римана и проблема Гольдбаха не разрешены по сей день и включены в число проблем Дэвида Гильберта, а первая признана одной из «проблем тысячелетия», за решение которой Математический институт Клэя (штат Массачусетс, США) пообещал миллион долларов.

Устройство Тьюринга, проверяющее теорию ZFC, получило название Z-машины и включает в себя 7918 состояний. Если теория ZFC непротиворечива, это устройство должно функционировать вечно. В противном случае машина прекратит свою работу. Как отмечает филдсовский лауреат Теренс Тао из Калифорнийского университета в Лос-Анджелесе (США), вечной работе Z-машины помешает физический износ и необходимость постоянного доступа энергии. Математик не беспокоится о возможной противоречивости теории ZFC.

Для этого уже существуют расширения теории ZFC, которые также могут быть проверены Z-машиной (и наоборот). Для проверки гипотезы Римана используется устройство Тьюринга с 5372 состояниями, а проблемы Гольдбаха — с 4888-ю. Если эти утверждения окажутся неправильными, машина остановится. «Можно подумать о той или иной системе аксиом как о компьютере с определенными ограничениями по объему памяти или мощности процессора, — говорит Тао. — Для данной задачи нельзя переключиться на компьютер с еще большей памятью, но независимо от того, насколько большой объем дискового пространства на компьютере имеется, будут по-прежнему существовать задачи, которые выходят за рамки его возможностей».

В апреле 2016 года математики опубликовали коды устройств в препринте и предлагают всем желающим приступить к их упрощению. Ученых интересует вопрос: есть ли машина Тьюринга с минимально возможным числом состояний (то есть устроенная наиболее примитивно), благодаря которой было бы возможно проверить непротиворечивость теории ZFC? Аронсон и Едиди пока не собираются реализовывать машину Тьюринга физически, но не исключают, что другие ученые или они сами впоследствии займутся и этим.