47 176 870 шагов: энтузиасты из интернета доказали пятое число «усердного бобра»
47 176 870 — столько шагов делает самая «трудолюбивая» из простейших компьютерных программ с пятью состояниями, прежде чем остановиться. Это число назвали пятым числом «усердного бобра», BB(5), и последние сорок лет его считали лишь вероятным ответом. Окончательно доказать его удалось не академическому институту, а интернет-сообществу энтузиастов, многие из которых не имеют научных степеней. А проверял доказательство компьютер — строчка за строчкой.
Задачу придумал венгерский математик Тибор Радо в 1962 году. Возьмём машину Тьюринга — простейшую абстрактную модель компьютера. У неё есть бесконечная лента из клеток с нулями и единицами и головка с конечным числом состояний. На каждом шаге головка читает клетку, записывает 0 или 1, сдвигается влево или вправо и переходит в новое состояние — по заранее заданной таблице правил. Вопрос Радо: какая машина с n состояниями, запущенная на пустой ленте, проработает дольше всех, но всё-таки остановится? Наибольшее число шагов и есть BB(n).