В теории вычислимости, busy beaver () — машина Тьюринга с заданным числом состояний, которая, будучи запущенной на пустой ленте, совершает максимально возможное число шагов и останавливается.
Точнее, пусть детерминированной машине Тьюринга с n состояниями, работающей над двоичным алфавитом {0, 1}, на вход подаётся пустая лента (заполненная нулями). Такая машина либо будет работать бесконечно долго, либо завершит свою работу за конечное время; в последнем случае мы определяем как максимальное количество шагов, которое совершит такая машина перед остановкой. Альтернативно, вместо количества шагов мы можем максимизировать количество единиц, записанных на ленте до момента остановки, При этом, вообще говоря, максимизироваться эти величины могут различными машинами Тьюринга..
В силу алгоритмической неразрешимости проблемы остановки, обе функции и являются невычислимыми, т.е. не существует алгоритма, вычисляющего их для любого n; более того, они растут быстрее, чем любая вычислимая функция. Их значение известно лишь вплоть до n = 5 и получено путём перебора всех возможных машин Тьюринга с заданным числом состояний и доказательства для каждой из них, останавливается ли она или нет: n1234567S(n)1621107> 2↑↑↑5Здесь мы используем стрелочную нотацию Кнута>2↑¹¹2↑¹¹3Σ(n)146134098> 2↑↑↑5>2↑¹¹2↑¹¹3
Примечания
Категория:Теория алгоритмов Категория:Неразрешимые проблемы Категория:Большие числа