Skip to main content
edited tags
Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114
edited tags
Link
Asaf Karagila
  • 39.8k
  • 8
  • 135
  • 283
Source Link
Dan
  • 1.3k
  • 1
  • 12
  • 15

On fast-growing hierarchy

Is there exists a recursively enumerable set of computable total fast-growing functions $(\mathbb N \rightarrow \mathbb N)$ such, that this set has no upper boundary in the set of all such functions (up to a dominance relation)?

Clearly, you can't enumerate some set of such functions in increasing order since diagonalization gives computable upper boundary, but what if we enumerate functions in some unknown order?