[Перевод] Как самые медленные компьютерные программы проливают свет на фундаментальные ограничения математики
Как правило, программисты хотят минимизировать время выполнения кода. Но в 1962 году венгерский математик Тибор Радо поставил противоположную задачу. Он задался вопросом: как долго может выполняться простая компьютерная программа, прежде чем она закончит работу? Радо назвал эти максимально неэффективные, но все же функциональные программы «усердными бобрами».
Поиск таких программ — жутко отвлекающая головоломка для программистов и других любителей математики с тех пор, как она была обнародована в колонке Computer Recreations в журнале Scientific American в 1984 году. Но за последние несколько лет игра в усердного бобра, как её называют, сама по себе стала объектом изучения, поскольку она связана с самыми возвышенными понятиями и открытыми проблемами в математике.
Цель игры «Усердный бобёр» — найти компьютерную программу, которая работает максимально долго. Её поиски удивительным образом связаны с некоторыми глубочайшими вопросами и понятиями в математике.
Визуализация виртуальной машины Тьюринга с пятью правилами, которая на сегодня работает дольше всего. Каждый столбец пикселей представляет собой один шаг в вычислениях, если двигаться слева направо. Чёрные квадраты показывают, где машина распечатала 1. В крайнем правом столбце показано состояние вычислений, в котором машина Тьюринга останавливается.
«В математике очень тонка граница между забавным отдыхом и тем, что на самом деле важно», — рассказывает Scott Aaronson, ученый-теоретик в области вычислительной техники из Техасского университета в Остине, который недавно опубликовал опрос о прогрессе в BusyBeaverology («Усердной бобрологии»).
Последние работы свидетельствуют о том, что поиск долго выполняемых компьютерных программ может пролить свет на состояние математических знаний и даже рассказать о том, что познаваемо. По мнению исследователей, игра в бобра даёт конкретный ориентир для оценки сложности определённых проблем, таких как нерешённая гипотеза Гольдбаха и Римана [восьмая проблема Гильберта]. Она даже даёт представление о том, где рушится логический фундамент математики. Логик Курт Гёдель доказал существование такой математической терра инкогнита почти сто лет назад. Но усердный бобёр может показать, где на числовой прямой она лежит на самом деле, как на древней карте, изображающей край света.
Невычислимая задача
Усердные бобры на самом деле — о поведении машин Тьюринга — примитивных, идеализированных компьютерах, придуманных Аланом Тьюрингом в 1936 году. Машина Тьюринга выполняет действия на бесконечной ленте, разделённой на квадраты. Она делает это согласно списку правил. Например, так может звучать первое правило:
Если квадрат содержит 0, заменить его на 1, сдвинуть один квадрат вправо и обратиться к правилу 2. Если квадрат содержит 1, оставить 1, сдвинуть один квадрат влево и обратиться к правилу 3.
У каждого правила есть эта вилка в стиле «выбирай свои приключения». Некоторые правила говорят о переходе к предыдущим правилам; Тьюринг доказал, что при наличии правильных инструкций и достаточного количества времени этот простой компьютер способен выполнять любые возможные вычисления.
Как отметил Тьюринг в 1936 году, для того чтобы что-то вычислить, машина Тьюринга в конечном счёте должна остановиться — она не может застрять в бесконечном цикле. Но он также доказал, что не существует надёжного, воспроизводимого способа отличить машины, которые останавливаются, от машин, которые просто работают вечно, — этот факт известен как проблема остановки.
Игра в усердного бобра ставит вопрос: учитывая определённое количество правил, какое максимальное количество шагов может сделать машина Тьюринга перед остановкой?
Тибор Радо, изображённый на недатированной фотографии, изобрёл усердного бобра как способ конкретизировать теоретическое представление о невычислимости.
Например, если вам разрешено только одно правило и вы хотите гарантировать, что машина Тьюринга останавливается, вы должны немедленно включить инструкцию остановки. Поэтому бобровое число машины с одним правилом, или BB (1), — это 1.
Но добавление всего лишь нескольких правил мгновенно взрывает количество возможных машин, которые нужно учитывать. Из 6561 возможной машины с двумя правилами самая длинная — шесть шагов перед остановкой — это число усердного бобра. А некоторые другие просто выполняются вечно. Ни одна из них не является усердным бобром, но как окончательно исключить их? Тьюринг доказал, что нет никакого способа автоматически определить, не остановится ли машина, которая работает в течение тысячи или миллиона шагов.
Вот почему найти числа усердных бобров столь трудно. Нет общего подхода к определению наиболее долго работающих машин Тьюринга с произвольным количеством инструкций; нужно ломать голову над спецификой каждого случая. Другими словами, игра в усердного бобра в общем-то «невычислима».
Доказать, что BB (2) = 6 и BB (3) = 107, было настолько сложно, что студент Радо Шэнь Линь получил докторскую степень за свою работу в 1965 году. Радо считал задачу BB (4) «совершенно безнадёжной», но задача была окончательно решена в 1983 году. За этими числами значения практически взрываются. Исследователи определили, например, что машина Тьюринга с пятью правилами работает 47 176 870 шагов перед остановкой, таким образом, число BB (5) по крайней мере не меньше этого. BB (6) составляет по крайней мере 7,4 × 1 036 534. «Нахождение точных значений нуждается в новых идеях и новых знаниях, если оно вообще возможно,» — рассказывает Ааронсон.
Порог неизвестности
Уильям Гасарх, учёный-компьютерщик из Университета Мэриленда, Колледж-Парк, сказал, что перспектива закрепления за числами усердных бобров «общего представления о том, что они действительно невычислимы», не так интересна ему. Он и другие математики в основном заинтересованы в использовании игры в качестве эталона для оценки сложности важных открытых проблем в математике или для выяснения того, что вообще познаваемо математически.
Например, гипотеза Гольдбаха задаётся вопросом, не является ли каждое чётное число больше 2, суммой двух простых чисел. Доказательство истинности или ложности предположения было бы эпохальным событием в теории чисел, позволяющим математикам лучше понять распределение простых чисел. В 2015 году пользователь GitHub под псевдонимом Code Golf Addict опубликовал код машины Тьюринга с 27 правилами, которая останавливается, если (и только если) догадка Гольдбаха является ложной. Она работает, считая вверх по всем чётным числам больше 4; для каждого из них она перебирает все возможные способы получить целое число, складывая два других и проверяя, являются ли два числа простыми. Когда она находит подходящую пару простых чисел, то переходит к следующему чётному числу и повторяет процесс. Если она находит чётное целое число, которое не может быть суммой пары простых чисел, то она останавливается.
Запуск этой бездумной машины — непрактичный способ разрешения гипотезы, потому что мы не можем узнать, остановится ли машина когда-нибудь, пока она не остановится. Но усердные бобры проливают свет на задачу. Если бы можно было вычислить BB (27), это дало бы потолок того, как долго нам придётся ждать, пока гипотеза Гольдбаха не будет разрешена автоматически. BB (27) соответствует максимальному количеству шагов, которые должна была бы выполнить эта машина Тьюринга с 27 правилами, чтобы остановиться (если бы она когда-нибудь это сделала). Если бы мы знали это число, мы могли бы запустить машину Тьюринга ровно на столько шагов. Если бы выполнение прекратилось к этому моменту, мы бы знали, что гипотеза Гольдбаха была ложной. Но если бы машина прошла так много шагов и не остановилась, мы бы точно знали, что она никогда не остановится, доказывая, таким образом, правдивость догадки.
Загвоздка в том, что число BB (27) — настолько непостижимо огромное число, что даже записать его, а тем более запустить фальсифицирующую машину Гольдбаха на такое количество шагов не представляется физически возможным в нашей Вселенной. Тем не менее данное непостижимо большое число — это точная цифра, чья величина, по словам Ааронсона, представляет собой «выражение современного знания» теории чисел.
В 2016 году Ааронсон установил подобный результат в сотрудничестве с Юрием Матиясевичем и Стефаном О'Риром. Они определили машину Тьюринга с 744 правилами, которая останавливается, если и только если гипотеза Римана является ложной. Гипотеза Римана также касается распределения простых чисел и является одной из гипотез Института математики Клэя, «Проблем тысячелетия» с решением стоимостью в $ 1 000 000. Машина Ааронсона даст автоматическое решение с помощью BB (744). Она работает по сути тем же бездумным процессом, что и машина Гольдбаха: итерация вверх до тех пор, пока не найдёт контрпример.
Конечно, BB (744) — это ещё более недостижимо большое число, чем BB (27). Но работа над тем, чтобы дать объяснение чему-то более простому, например BB (5), по словам Ааронсона, может на самом деле привести к появлению новых вопросов теории чисел, которые интересны сами по себе. Например, математик Паскаль Мишель [Pascal Michel] доказал в 1993 году, что записывающая машина Тьюринга с пятью правилами демонстрирует поведение, аналогичное поведению функции, описанной в гипотезе Коллаца, еще одной известной открытой задаче в теории чисел.
«За вопросом: «Остановится ли машина Тьюринга?» скрыто много вопросов математики, — сказал Ааронсон. — Если бы мы знали все числа усердного бобра, то могли бы решить все эти вопросы».
Совсем недавно Ааронсон использовал мерку чисел усердного бобра для измерения того, что он называет «порогом непознаваемости» для систем математики вообще. Знаменитые теоремы неполноты 1931 года доказали, что любой набор базовых аксиом, которые могли бы служить возможной логической основой математики, обречён на одно из двух: либо аксиомы будут противоречивыми, что приведёт к противоречиям (например, доказывая, что 0 = 1), либо они будут неполными, неспособными доказать некоторые истинные утверждения о числах (например, тот факт, что 2 + 2 = 4). Аксиоматическая система, лежащая в основе почти всей современной математики, известная как теория множеств Цермело-Френкеля (далее — ZF), имеет свои собственные гёделевы ограничения; и Ааронсон хотел использовать усердных бобров, чтобы установить, где эти границы находятся.
В 2016 году он и его аспирант Адам Едидия определили машину Тьюринга с 7,910 правилом, которая остановится только в том случае, если теория множеств ZF противоречит самой себе. Это означает, что расчёт BB (7,910) — это вычисление, ускользающее от аксиом теории множеств ZF. Эти аксиомы не могут применяться, чтобы доказать, что BB (7,910) представляет одно число, а не другое; это похоже на невозможность доказать, что 2 + 2 = 4, а не 5.
О'Рир впоследствии разработал гораздо более простую машину в 478 правил, которая останавливается, если ZF непоследовательна, — по сути передвигая порог неизвестности ближе, от BB (7,910) до BB (748). «Это своего рода преувеличение, что число [правил] выглядит так серьезно», — сказал Харви Фридман, математик-логик, заслуженный профессор Университета штата Огайо. Фридман думает, что это число можно уменьшить еще больше: «Я думаю, может быть, правильный ответ — 50». Ааронсон подозревает, что истинный порог может быть так же близок, как BB (20).
Близко или далеко, такие пороги неизвестности определённо существуют. «Это видение мира, которое у нас было со времён Гёделя, — сказал Ааронсон. — Функция усердного бобра — это еще один способ конкретизировать его».
КУРСЫ
