Skip to main content
2 of 2
moved question from title to text
YCor
  • 63.9k
  • 5
  • 187
  • 286

Do all non-computable functions grow faster than computable functions?

Do all non-computable functions grow faster than computable functions?

In Does the Busy Beaver function grow faster than the Tree function?, the informal proof hinges on non-computable functions such as Busy Beaver growing faster than computable ones such as TREE. Is this necessarily given? For example, a trivially non-computable function which grows slower than TREE would be the sum of reciprocals of Busy Beaver: $$\sum_{i=1}^n\frac{1}{BB(n)}$$

l0b0
  • 109
  • 4