1-Y sequence (better known as simply Y sequence) is a recursive function that is so recursive that we didn't know if it could terminate.
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.
nkochavi•40m 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.