BusyBeaver(5) составляет 47,176,870

Особенность функции BusyBeaver в том, что ее очень легко понять, но очень сложно вычислить. Сейчас мы знаем ее значение до 5, что не является большим прогрессом для более чем 50-летней работы.

Если вы знаете, что такое машина Тьюринга, то проблема "занятого бобра" - одна из тех удивительно простых проблем, которые, как оказалось, имеют глубокие и удивительные связи и последствия.

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

Обратите внимание, что машины Тьюринга, которые не останавливаются, не считаются, потому что они выполняют бесконечное количество шагов. Это важный момент, потому что машина Тьюринга с небольшим числом состояний может работать очень долго, просто переходя из одного состояния в другое, но требование, чтобы машина остановилась, означает, что что-то должно измениться, чтобы условие остановки могло быть выполнено. Рассмотрим проблему написания программы с небольшим числом операторов, чтобы она в конце концов остановилась - каково максимальное время выполнения?

В 1960-х годах было быстро доказано, что BB(1)=1, BB(2)=6 и BB(3)=21. Небольшое количество состояний позволило провести полный поиск. Только в 1983 году Аллен Брэди догадался, что BB(4)=107, и вот диаграмма состояний машины Тьюринга, которая работает для BB(4):

После этого все затихло, несмотря на то, что многие занимались этой проблемой.

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

Конечные или ограниченные вещи всегда вычислимы. Например, если вы ограничиваете размер машины Тьюринга числом n, то проблема остановки вычислима для этого n. Только когда вы требуете решения для всех n, или, лучше, для неограниченных n, проблема становится невычислимой.

Теперь у нас есть результат, указанный в заголовке:

BB(5)=47 176 870.

То есть наибольшее время, которое может проработать пятисоставная машина Тьюринга, составляет 47 176 870 шагов или переходов между состояниями.

Результат был окончательно доказан международной коллаборацией под названием bbchallenge, которая решила эту задачу с помощью системы доказательств Coq. Существует примерно (4n + 4)2n машин Тьюринга на n состояний, и это делает количество машин для n=5:

10,240,000,000,000

Затем возникает проблема, как долго ждать, прежде чем решить, что машина не остановится. Машина с 5 состояниями, открытая Юргеном Бунтроккой, работает ровно 47 176 870 раз. Это была машина-чемпион, и если не удалось найти пятисоставную машину с остановками, которая дала бы большее значение, то мы решили проблему. Другими словами, если машина работает дольше, чем чемпион, то она либо не останавливается, либо становится новым чемпионом.

Интересно, что машина, работающая в течение BB(5), - это машина с пятью состояниями, которая вычисляет:

• g(x) = (5x+18)/3, если x = 0 (mod 3),
• g(x) = (5x+22)/3, если x = 1 (mod 3),
• g(x) = HALT, если x = 2 (mod 3).

Если вы знакомы с конъектурой Коллатца, то поймете, что она очень похожа - и в этом случае доказательно достигается HALT.

Теперь команда сосредоточилась на вычислении BB(6), и кажется вероятным, что это никогда не будет завершено, поскольку число машин на шесть состояний велико, и мы уже знаем, что BB(6) по крайней мере 10 возведено в степень 10 пятнадцать раз.

В чем смысл всего этого?

Чтобы исследовать границы вычислимого и то, как быстро растет сложность при масштабировании простых систем? Нет, не совсем, это просто весело...

Майк Джеймс - автор книги The Programmer's Guide To Theory, в которой в неформальной, но информативной форме излагаются фундаментальные идеи компьютерной науки. Его последняя книга - The Trick Of The Mind: Programming and Computational Thought, предназначенная как для программистов, так и для непрограммистов, рассматривает природу программирования и объясняет, почему это совершенно особый навык.