3 ms·
Another sequence that's about as simple to define as Goodstein's is the following: Start with any binary tree, which is either 0, or a pair [s,t] of binary tree
by tromp 3y ago
Another sequence that's about as simple to define as Goodstein's is the following:
Start with any binary tree, which is either 0, or a pair [s,t] of binary trees.
Then while it's not 0, repeatedly apply the following predecessor operation P on binary trees:
P([0,t]) = t
P([s,t]) = [P(s),t] but with all instances of t replaced by [P(s),t]
For example, starting from [[0,0],0], we have the sequence of predecessor trees
[[0,0],0]
[[0,0],[0,0]]
[0,[0,[0,0]]]
[0,[0,0]]
[0,0]
0
This sequence grows unbelievably faster than Goodstein's, and even faster than the infamous TREE() function [1], while having an almost trivial definition. The number of predecessors to reach 0 is sequence A367433 in the Online Encyclopedia of Integer Sequences [2].
[1] https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE_function https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE_...
[2] https://oeis.org/A367433 https://oeis.org/A367433
- Sharlin 3y agoWorth noting that this sequence was introduced, of all places, as an answer to a codegolf.stackexchange question in 2021! https://codegolf.stackexchange.com/a/219466 https://codegolf.stackexchange.com/a/219466
- tromp 3y agoIndeed; a lot of gems are to be found there. Like this 49 bit program to exceed Graham's Number [1]. [1] https://codegolf.stackexchange.com/questions/6430/shortest-terminating-program-whose-output-size-exceeds-grahams-number/263884#263884 https://codegolf.stackexchange.com/questions/6430/shortest-t...
- dandanua 3y agoThis function is almost like in the definition of middle-growing hierarchy https://googology.fandom.com/wiki/Middle-growing_hierarchy https://googology.fandom.com/wiki/Middle-growing_hierarchy But this hierarchy can be defined for any ordinal with a system of notations. I'm wondering if there is some deeper sense in this Patcail's predecessor function? Are there some follow up research on that?
- wruza 3y agoLast 4 terms are trivial. But I have trouble following even the first step. The SE answer is also pretty comprehensible, but as if there was some default assumption I’m not aware of. Do we make one-time substitution, or recursive? Stopping rules feel arbitrary in all enumeration combinatorics I try. https://codegolf.stackexchange.com/a/219466 https://codegolf.stackexchange.com/a/219466
- dandanua 3y agoJust look at the expanded js code, I also had troubles with the more informal description. It's a one-time substitution but for all matches.
- tromp 3y agoThe first step proceeds as follow. We want the predecessor of [s,t] with s=[0,0] and t=0. We first compute s' = P(s) = P([0,0]) = 0. Then in [s',t] = [0,0] we must replace all occurrences of 0 with [0,0], which results in [[0,0],[0,0]]. This is a one-time substitution (else it would never end).