Пример алгоритмически не разрешимой проблемы: по данному коду машины Тьюринга определить, остановится она через конечное число шагов или нет, будучи запущенной на пустой ленте.
В связи с этой проблемой рассматривается функция

максимальное количество шагов до остановки. Максимум берется по всем машинам Т. с кодом длины

, которые
останавливаются .
Очевидно,

-- не убывающая функция.
Эта функция не является ОРФ (обще-рекурсивной функцией), потому что если бы у нас был алгоритм, вычисляющий её для любого

, то, имея код МТ длины

, мы бы посчитали

, запустили бы эту МТ и посмотрели, остановится она за

шагов или нет. Остановится -- хорошо, не остановится -- значит не остановится и дальше по определению

.
Точно также показывается, что

не может иметь обще-рекурсивную мажоранту, т.е. не существует ОРФ

такой, что для всех натуральных

выполнено

.
Это означает, что

в некотором смысле растет очень быстро.
Вопрос состоит в следующем:
верно ли , что

начиная с некоторого номера обгоняет любую ОРФ?
Точнее: верно ли, что для любой ОРФ

найдется номер

такой, что при

?
Если для

это и не так, то существуют ли вообще такие функции?