Skip to main content
2 of 3
edited tags
Asaf Karagila
  • 39.8k
  • 8
  • 135
  • 283

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?

Dan
  • 1.3k
  • 1
  • 12
  • 15