Деловой бобер
В теоретической информатике игра « Бобер» направлена на поиск завершающей программы заданного размера, которая производит максимально возможный результат. [1] Поскольку программу с бесконечным циклом , производящую бесконечный вывод, легко представить, такие программы исключены из игры.
Точнее, игра в занятого бобра состоит из разработки останавливающейся машины Тьюринга с алфавитом {0,1}, которая записывает на ленту наибольшее количество единиц, используя только заданный набор состояний. Правила игры с двумя состояниями следующие:
Игрок должен составить таблицу переходов, стремясь к максимальному выводу единиц на ленте, при этом удостоверившись, что машина в конце концов остановится.
n -й занятый бобер , BB - n или просто «занятый бобер» — это машина Тьюринга, которая выигрывает игру «Занятый бобер» с n состояниями. То есть он достигает наибольшего числа единиц среди всех других возможных конкурирующих машин Тьюринга с n состояниями. Например, машина Тьюринга BB-2 достигает четырех единиц за шесть шагов .
Определить, является ли произвольная машина Тьюринга занятым бобром, неразрешимо . Это имеет значение в теории вычислимости , проблеме остановки и теории сложности . Эта концепция была впервые введена Тибором Радо в его статье 1962 года «О невычислимых функциях». [1]
Игра занятого бобра с n -состояниями (или игра BB - n ), представленная в статье Тибора Радо 1962 года, включает в себя класс машин Тьюринга , каждый элемент которых должен соответствовать следующим конструктивным требованиям:
