Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Well, the goal is to get as close to infinity as possible with the smallest program possible. We can name big numbers just fine, by recursing over recursion for some number of steps, but the fun part is to have these fall out 'naturally' from the space of small Turing machines.

In this case, we can actually name the number of symbols in terms of Knuth's up-arrow notation [0], which describes the sequence of operations starting with multiplication, exponentiation, repeated exponentiation (called tetration, e.g., 2↑↑5 = 2^[2^[2^[2^2]]]), repeated tetration (called pentation, e.g., 2↑↑↑5 = 2↑↑[2↑↑[2↑↑[2↑↑2]]]), and so on. This number is big enough that it needs 15 arrows in a row to describe it reasonably. So it's not just that the number is very large, it's that we can also put a neat lid over its value. For instance, we know it's still nothing compared to Graham's number, which can't be described with any reasonable number of up-arrows.

[0] https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation



Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10

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

Search: