Эта машина Тьюринга должна работать вечно, если только математика не ошибается
Алан Тьюринг: его тень до сих пор нависает над математикой
Сто пятьдесят лет математики будут опровергнуты, если новая компьютерная программа перестанет работать. К счастью, это маловероятно, но код, лежащий в её основе, проверяет границы математической области.
Программа представляет собой имитацию машины Тьюринга — математической модели вычислений, созданной криптографом Аланом Тьюрингом. В 1936 году он показал, что действия любого компьютерного алгоритма можно имитировать с помощью простой машины, которая считывает и записывает нули и единицы на бесконечно длинной ленте, проходя через набор состояний или инструкций. Чем сложнее алгоритм, тем больше состояний требуется машине.
Теперь Скотт Ааронсон и Адам Йедидия из Массачусетского технологического института создали три машины Тьюринга, поведение которых связано с глубокими математическими вопросами. В их число входит доказательство 150-летней гипотезы Римана, которая, как считается, определяет закономерности распределения простых чисел.
Машины Тьюринга уже давно используются для решения подобных задач. Их появление связано с рядом философских открытий, которые потрясли математический мир в 1930-х годах. Во-первых, Курт Гёдель доказал, что некоторые математические утверждения невозможно доказать истинными или ложными — они неразрешимы. По сути, он создал математическую версию предложения «Это предложение ложно»: логическую головоломку, которая противоречит сама себе.
В утверждении Гёделя есть лазейка. Если изменить базовые допущения, на которых строятся доказательства, — аксиомы, — то проблему можно будет решить. Но при этом останутся другие неразрешимые проблемы. Это значит, что не существует аксиом, которые позволили бы доказать всё.
Следуя аргументам Гёделя, Тьюринг доказал, что должны существовать машины Тьюринга, поведение которых невозможно предсказать в рамках стандартных аксиом, известных как теория множеств Цермело — Френкеля с аксиомой выбора (C) или, проще говоря, ZFC, лежащая в основе большей части математики. Но мы не знали, насколько сложными они должны быть.
Йедидия и Ааронсон создали машину Тьюринга с 7918 состояниями, обладающую этим свойством. Они назвали её «Z».
«Мы попытались конкретизировать и сказать, сколько состояний нужно пройти, прежде чем вы окажетесь в этой бездне недоказуемости?» — говорит Ааронсон.
По словам Теренса Тао из Калифорнийского университета в Лос-Анджелесе, пара смоделировала Z на компьютере, но она настолько мала, что теоретически её можно создать в виде физического устройства. «Если включить такую физическую машину, то, по нашему мнению, она будет работать бесконечно», — говорит он, предполагая, что можно не учитывать физический износ или требования к энергопотреблению.
Z запрограммирован на бесконечный цикл из 7918 инструкций, но если бы он в конце концов остановился, это доказало бы несостоятельность ZFC. Однако математики не стали бы слишком паниковать — они могли бы просто перейти к более строгому набору аксиом. Такие аксиомы уже существуют, и их можно было бы использовать для доказательства поведения Z, но это мало что даст, потому что всегда найдётся машина Тьюринга, которая превзойдёт любую аксиому.
«Любую систему аксиом можно представить в виде компьютера с определённым ограниченным объёмом памяти или вычислительной мощностью, — говорит Тао. — Можно перейти на компьютер с ещё большим объёмом памяти, но, каким бы большим ни был объём памяти компьютера, всё равно найдутся задачи, которые он не сможет выполнить».
Но Ааронсон и Йедидия создали ещё две машины, которые могут заставить математиков задуматься. Они остановятся только в том случае, если две известные математические задачи, которые долгое время считались верными, на самом деле неверны. Это гипотеза Гольдбаха, которая гласит, что любое чётное число, большее двух, является суммой двух простых чисел, и гипотеза Римана, которая утверждает, что все простые числа подчиняются определённому закону. Последняя лежит в основе некоторых разделов современной теории чисел, и её опровержение стало бы серьёзным, хоть и маловероятным, событием.
На самом деле у этой пары нет намерения бесконечно запускать свои машины Тьюринга в попытке доказать, что эти проблемы неразрешимы. По словам Лэнса Фортноу из Технологического института Джорджии в Атланте, это не самый эффективный способ решения этой проблемы.
Представление математических задач в виде машин Тьюринга имеет и другое практическое преимущество: оно помогает понять, насколько они сложны. Машина Гольдбаха имеет 4888 состояний, машина Римана — 5372, а машина Z — 7918, что позволяет предположить, что проблема ZFC является самой сложной из трёх. «Это соответствует интуитивным представлениям большинства людей о подобных вещах», — говорит Ааронсон.
Йедидия выложил свой код в открытый доступ, и теперь математики могут соревноваться в том, кто уменьшит размер этих машин Тьюринга до предела. Один из комментаторов блога Ааронсона SaiBlog уже заявил, что создал машину Гольдбаха с 31 состоянием, хотя пара ещё не проверила это.
Фортноу говорит, что фактический размер машин Тьюринга не имеет значения. «В статье говорится, что мы можем использовать очень сжатые описания, которые уже выходят за рамки ZFC, но даже если бы они были ещё более сжатыми, это не заставило бы нас усомниться в основах математики», — говорит он.
Но Ааронсон говорит, что дальнейшее уменьшение Z может рассказать кое-что интересное о границах основ математики — то, что, вероятно, хотели бы знать Гёдель и Тьюринг. «Они могли бы сказать: “Это хорошо, но можешь ли ты получить 800 состояний? А как насчёт 80 состояний?”» — говорит Ааронсон. «Я хотел бы знать, существует ли машина с 10 состояниями, поведение которой не зависит от ZFC».