Given that Graham's Number is an (over-)extension of the Ackermann-function that... | Hacker News

Hacker News new | past | comments | ask | show | jobs | submit

login

infogulch on April 28, 2016 | parent | context | favorite | on: On the (Small) Number of Atoms in the Universe

Given that Graham's Number is an (over-)extension of the Ackermann-function that means that it's still computable, correct?

Given the series leading up to Graham's Number, G = g_64 (g_1, g_2, ...), BB(n) will outgrow g_n, right? If so what's the smallest n such that BB(n) > g_n?

infogulch on April 28, 2016 [–]

After a bit of research I found that there is a proof [0][1] that BB(12) > g_1. But that's still a ways from g_2, let alone g_64.

[0]: "A Lower Bound on Rado's Sigma Function for Binary Turing Machines" by Milton Green (1964)

[1]: https://en.wikipedia.org/wiki/Busy_beaver#Known_values_for_....

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact