Вспомним, что BB(n), или «n-е число Делового Бобра», — это наибольшее число шагов, которые машина Тьюринга с n-состояниями может сделать на чистой первоначально ленте, прежде чем остановится.
Первой задачей было доказать, что BB(n) растет быстрее, чем какая бы то ни было вычислимая функция.
Предположим, что существует вычислимая функция f(n), такая, что f(n) > BB(n) для любого n. Тогда, имея машину Тьюринга M с n-состояниями, мы можем сначала вычислить f(n), а затем смоделировать работу M вплоть до f(n) — го шага. Если M не остановилась до этого момента, то мы можем быть уверены, что она не остановится никогда, потому что f(n) больше максимального числа шагов, которые может сделать произвольная машина с n-состояниями. Но это дает нам способ решить проблему остановки, что, как мы уже знаем, невозможно. Следовательно, функция f не существует.
Таким образом, функция BB(n) растет очень, очень, очень быстро. (На случай, если вам любопытно, приведу несколько ее первых значений, вычисленных неленивыми людьми, у которых слишком много свободного времени: BB(1) = 1, BB(2) = 6, BB(3) = 21, BB(4) = 107, BB(5) ≥ 47 176 870. Разумеется, эти значения зависят от конкретных деталей того, как определены машины Тьюринга.)
Второй задачей было определить, является ли
вычислимым действительным числом. Иными словами, существует ли алгоритм, который на основе положительного целого k выдает рациональное число S', такое, что |S — S'| < 1/k?
Что, эта задача оказалась посложнее для вас? Хорошо, давайте заглянем в ответ. Ответ отрицательный: это число не является вычислимым. Потому что, если предположить его вычислимость, мы получим алгоритм для вычисления самого BB(n), что, как мы знаем, невозможно.
Примем по индукции, что мы уже вычислили BB(1), BB(2),…, BB(n — 1). Тогда рассмотрим сумму «членов высшего порядка»:
Если S вычислимо, то Sn тоже должно быть вычислимым. Но это означает, что мы можем аппроксимировать Sn с точностью до 1/2, 1/4, 1/8 и так далее, до тех пор, пока интервал, в котором мы ограничили Sn, перестанет включать в себя 0. Когда это произойдет, мы получим верхнюю оценку для 1/Sn. Поскольку 1/BB(n + 1), 1/BB(n + 2) и т. п. намного меньше, чем 1/BB(n), любая верхняя оценка для 1/Sn немедленно выдает верхнюю оценку также и для BB(n). Но, получив верхнюю оценку для BB(n), мы можем вычислить и сам BB(n) путем простого моделирования всех машин Тьюринга с n-состояниями. Так что, считая, что мы умеем вычислять S, мы получаем возможность вычислить ВВ(n) (а мы уже знаем, что это невозможно). Следовательно, S не является вычислимым.