nkochavi 3 hours ago
Most recursive functions take an exponential amount of time to resolve. Some take much more time to resolve. A good example is the Kirby-Paris Hydra game, which given a starting Hydra of 5 nodes high takes longer to resolve than incrementing up to Graham's Number. It is proven that the game is always winnable by mapping to a countable ordinal less than epsilon naught, the proof theoretic ordinal of Peano Arithmetic.
But Y sequence is so explosive that it cannot be mapped to ordinals, it grows faster than any well-defined ordinal notation and cannot be proved to terminate under many axiomatic systems.
Please let me know if this is a relevant and/or good post to this site. It's a huge result in a very niche field.