Googology Wiki
Advertisement
Googology Wiki

Before I write down the formal definition, I want to explain it without formalties. Also Python code in the bottom.

Consider a function expand(S,n) such that it accepts an integer sequence (preferrably starting with 0) and another integer as input. S[i] denotes the (1+i)th element of S and S[-1] denotes the last element of S assuming it exists.

Since I didn't define "standard" yet I hope I don't accidentally mess something up.

if S is the empty sequence, expand(S,n)=n for every n.

let c = S[-1], and call it the "child". If c is the smallest element, expand(S,n) = S with the last element removed.

if c isn't the smallest element: find the rightmost element in S that's less than c. This is the same as the bad root in PrSS. Call it r0, or the "parent". Let d be 0 and call it "delta". Call everything to the right (including) of r0 the "family".

Begin a search from right to left in S, starting from r0, and let p=r0.

Whenever you see some element that's less than c-d: call it an "uncle node". If the difference between c and this uncle node is less than d, increment d. Finally, compare the subsequence "everything to the right of this uncle node including, incremented by d" and the family. If it's lexicographically larger or equal, reassign p to this uncle node and repeat. Otherwise, stop. If you reach the beginning also stop.

The bad root is the last value of p. Intuitively it's the last (leftmost) uncle node that, when "bumped" up to c-1, isn't lexicographically smaller than the family.

Current results suggest 0,1,2 does indeed correspond to G0 and under G0 there is a very, very nice correspondence to the binary veblen function. But beyond G0 stuff... behaves rather weird; Bashicu conjectured that 0,1,2,0,1,2 was G1 and 0,1,2,2 was BHO. Both are unlikely; 0,1,2,0,1,1,2 being BHO and 0,1,2,0,1,2 being ψ(Ω_ω) are possible. 0,1,2,1 might be OFP and the limit might be much larger than what Bashicu estimated: ψ(ψ_χ_ω(0)(0)). Edit: Oops. His original claim is S(x)=ψ_Ω(χ(ω,0)).

But those are only if SSS terminates at all. If we somehow manage to prove 0,1,2 is G0 by a correspondence with ordinals using veblen function, we know SSS under 0,1,2 terminates; above that I can't guarantee it terminates.

hope wikia doesn't mess up my code.

def SSS(S,n=2):
    def add(p,q):
        return [p[i] + q[i] for i in range(len(p))]
    if not(S):
        return n
    if S[-1] <= min(S):
        return S[:-1]
    d = 0
    r0 = max([i for i in range(len(S)) if S[i] < S[-1]])
    p = r0
    g = len(S)-r0
    for i in range(r0,-1,-1):
        if S[-1]-S[i] > d:
            d += (S[-1]-S[i] > d+1)
            if add(S[i:i+g],[d]*g) < S[r0:]:
                break
            p = i
    else:
        p = 0
    
    b = []
    for i in range(n):
        b += add(S[p:-1],[i*d]*len(S[p:-1]))
    return S[:p]+b
Advertisement