[tromp]

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_...

[2] https://oeis.org/A367433

[Sharlin]

Worth 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

[tromp]

Indeed; 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-t...

[dandanua]

This function is almost like in the definition of 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]

Last 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

[tromp]

The 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).

[Hugsun]

Couldn't you also do the substitution n times to make this ordinal emulate the fast growing hierarchy instead of the middle growing one?

[tromp]

Where would you get the number n from? All we have here are binary trees s and t of arbitrary shape.

[wruza]

Ah, now I see, thanks!

[dandanua]

Just 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.