Busy beaver
В теории вычислимости, busy beaver (рус. усердный бобр) — машина Тьюринга с заданным числом состояний, которая, будучи запущенной на пустой ленте, совершает максимально возможное число шагов и останавливается.
Точнее, пусть детерминированной машине Тьюринга с n состояниями, работающей над двоичным алфавитом {0, 1}, на вход подаётся пустая лента (заполненная нулями). Такая машина либо будет работать бесконечно долго, либо завершит свою работу за конечное время; в последнем случае мы определяем как максимальное количество шагов, которое совершит такая машина перед остановкой. Альтернативно, вместо количества шагов мы можем максимизировать количество единиц, записанных на ленте до момента остановки, [1].
В силу алгоритмической неразрешимости проблемы остановки, обе функции и являются невычислимыми, т.е. не существует алгоритма, вычисляющего их для любого n; более того, они растут быстрее, чем любая вычислимая функция. Их значение известно лишь вплоть до n = 5 и получено путём перебора всех возможных машин Тьюринга с заданным числом состояний и доказательства для каждой из них, останавливается ли она или нет[2][3]:
| n | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| S(n) | 6 | 21 | 107 | 47 176 870[4] | > 10⇈15[5][6] |
| Σ(n) | 4 | 6 | 13 | ≥ 4098[7] | > 10⇈15[5][6] |
Примечания
- ↑ При этом, вообще говоря, максимизироваться эти величины могут различными машинами Тьюринга.
- ↑ последовательность A060843 в OEIS
- ↑ последовательность A028444 в OEIS
- ↑ Brubaker, Ben. Amateur Mathematicians Find Fifth 'Busy Beaver' Turing Machine (англ.). Quanta Magazine (2 июля 2024).
- ↑ 1 2 Здесь мы используем стрелочную нотацию Кнута, 10⇈15 = 1010.·.·.·10.
- ↑ 1 2 Weisstein, Eric W. Busy Beaver. Wolfram MathWorld. Архивировано 7 декабря 2023 года.
- ↑ Ben-Amram, A. M.; Petersen, H. (2002). Improved bounds for functions related to busy beavers. Theory of Computing Systems. 35 (1): 1–11. doi:10.1007/s00224-001-1052-0. MR 1879169.