Быстрорастущая иерархия

Быстрорастущие иерархии функций — это системы функций, которые растут быстрее, чем любая вычислимая функция.
Иерархии быстрорастущих функций включают иерархии Гжегорчика, Вайнера и другие.
Каждая функция в быстрорастущей иерархии является полной вычислимой функцией.
В иерархии Вайнера каждая функция fa доминирует над fβ, если α < β.
В каждой вычислимой функции, доказуемо полной в арифметике Пеано, доминирует некоторый fa с α < ε0 в иерархии Вайнера.
Функция Гудштейна имеет примерно такую же скорость роста, как fe0 в иерархии Вейнера.
В иерархии Вайнера, если α < β < ε0, то fβ доминирует над каждой вычислимой функцией во времени и пространстве, ограниченных некоторой фиксированной итерацией fak.

Полный текст статьи:

Быстрорастущая иерархия — Википедия