Пусть BB (n), или «n-е число Делового Бобра», — это максимальное число шагов, которые машина Тьюринга с n-состояниями может сделать на пустой первоначально ленте, прежде чем остановится. (Здесь максимум берется по всем машинам Тьюринга с n-состояниями, которые рано или поздно остановятся.)

1. Докажите, что BB (n) растет быстрее, чем любая вычислимая функция.

2. Пусть S = 1/BB (1) + 1/BB (2) + 1/BB (3) + …

Является ли S вычислимым действительным числом? Иными словами, существует ли алгоритм, который, получив на вход положительное целое число k, выдаст на выходе рациональное число S′, такое, что |S — S′| < 1/k?