Функция Busy beaver (усердный бобёр) считается важной в теории вычислимости, потому что она является примером невычислимой функции. 24

Это максимальное количество шагов, которое компьютерная программа может сделать перед остановкой, если у неё есть n состояний, где состояния означают сложность задачи. 2 Значения этой функции, называемые BB(n), никогда не будут известны для всех величин n. 2 Чтобы узнать её значение, необходимо полностью перебирать все возможные варианты, что требует нереальных вычислительных мощностей. 4

Кроме того, если бы было возможно вычислить значения функции Busy beaver для всех n, то это разрешило бы все математические догадки, которые можно закодировать в форме «останавливается ли эта машина Тьюринга». 5