Busy beaver
В теории вычислимости, busy beaver (рус. усердный бобр) — машина Тьюринга с заданным числом состояний, которая, будучи запущенной на пустой ленте, совершает максимально возможное число шагов и останавливается.
Точнее, пусть детерминированной машине Тьюринга с n состояниями, работающей над двоичным алфавитом {0, 1}, на вход подаётся пустая лента (заполненная нулями). Такая машина либо будет работать бесконечно долго, либо завершит свою работу за конечное время; в последнем случае мы определяем как максимальное количество шагов, которое совершит такая машина перед остановкой. Альтернативно, вместо количества шагов мы можем максимизировать количество единиц, записанных на ленте до момента остановки, [1].
В силу алгоритмической неразрешимости проблемы остановки, обе функции и являются невычислимыми, т.е. не существует алгоритма, вычисляющего их для любого n; более того, они растут быстрее, чем любая вычислимая функция. Их значение известно лишь вплоть до n = 5 и получено путём перебора всех возможных машин Тьюринга с заданным числом состояний и доказательства для каждой из них, останавливается ли она или нет[2][3]:
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| S(n) | 1 | 6 | 21 | 107 | 47 176 870 | > 2↑↑↑5[4][5] | >2↑¹¹2↑¹¹3[4][6] |
| Σ(n) | 1 | 4 | 6 | 13 | 4098 | > 2↑↑↑5[4][5] | >2↑¹¹2↑¹¹3[4][6] |