23
\$\begingroup\$

As a follow up to Shortest terminating program whose output size exceeds Graham's number and Golf a number bigger than TREE(3), I present a new challenge.

Loader's number is a very large number, that is kind of hard to explain (since it was itself the result of a code golfing exercise with a flexible goal). There is a definition and explanation here, but for the purposes of self-containment, I will attempt to explain it later in this post as well.

The algorithm Ralph Loader used produces one of the largest numbers of any (computable) algorithm ever written! Indeed, Loader's number is the largest "computable" number on the Googology Wiki. (By "computable" number, they mean a number defined in terms of a computation.) That means that if answer produces a number larger than Loader's number in an interesting way (i.e. not just Loader's number+1), you could go down in Googology history! That being said, programs that produce something like Loader's number+1 are definitely valid answers and contenders to this question; just don't expect any fame.

Your job is to create a terminating program that produces a number larger than Loader's number. This is , so the shortest program wins!

  • You aren't allowed to take input.
  • Your program must eventually terminate deterministically but you can assume the machine has infinite memory.
  • You may assume your language's number type can hold any finite value but need to explain how this exactly works in your language (ex: does a float have infinite precision?)
    • Infinities are not allowed as output.
    • Underflow of a number type throws an exception. It does not wrap around.
  • You need to provide an explanation of why your number is so big and an ungolfed version of your code to check if your solution is valid (since there is no computer with enough memory to store Loader's number).

So here is an explanation of Loader's number. See http://googology.wikia.com/wiki/Loader%27s_number and the links therein for more precise details. In particular, it contains a program that produces Loader's number exactly (by definition).

The calculus of constructions is essentially a programming language with very particular properties.

First of all, every syntactically valid program terminates. There are no infinite loops. This will be very useful, because it means that if we run an arbitrary calculus of constructions program, our program will not get stuck. The problem is that this implies the calculus of constructions is not Turing complete.

Second of all, among non-Turing complete languages, it is one of the most powerful. Essentially, if you can prove that a Turing machine will halt on every input, you can program a function in the calculus of constructions that will simulate it. (This does not make it turing complete, because there are halting turing machines that you can not prove are halting.)

Loader's number is essentially a busy beaver number for the calculus of constructions, which is possible to compute since all coc programs terminate.

In particular, loader.c defines a function called D. Approximately, D(x) iterates over all bit-strings less than x, interprets them as a coc programs, runs the syntactically valid ones, and concatenates the results (which will also be bitstrings). It returns this concatenation.

Loader's number is D(D(D(D(D(99))))).

A more readable copy of the code from the googolology wiki

int r, a;

P(y,x){return y- ~y<<x;}

Z(x){return r = x % 2 ? 0 : 1 + Z (x / 2 );}

L(x){return x/2 >> Z(x);}

S(v,y,c,t){
   int f = L(t);         
   int x = r;
   return f-2 ? f>2 ? f-v ? t-(f>v)*c : y : P(f,P(S(v,y,c,L(x)), S(v+2,t=S(4,13,-4,y),c,Z(x)))) : A(S(v,y,c,L(x)),S(v,y,c,Z(x)));
}

A(y,x){return L(y)-1 ? 5<<P(y,x) : S(4,x,4,Z(r));}

D(x) 
{
   int f;
   int d;
   int c=0;
   int t=7;
   int u=14;
   while(x&&D(x-1),(x/=2)%2&&(1)){
      d = L(L(D(x))),
      f = L(r),
      x = L(r),
      c - r||(L(u)||L(r)-f||(x/=2)%2&&(u=S(4,d,4, r),t=A(t,d)),f/2&(x/=2)%2&&(c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u))),
      c&&(x/=2)%2&&(t=P(~u&2|(x/=2)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r)
      u/2&(x/=2)%2&&(c=P(t,c),u=S(4,13,-4,t),t=9);
    }
    return a = P( P( t, P( u, P( x, c)) ),a);
}

main(){return D(D(D(D(D(99)))));}
\$\endgroup\$
18
  • 1
    \$\begingroup\$ You know Googology Wiki? I'm MilkyWay90 there! \$\endgroup\$
    – MilkyWay90
    Dec 3 '18 at 23:39
  • 1
    \$\begingroup\$ @MilkyWay90 oh, cool. \$\endgroup\$
    – PyRulez
    Dec 3 '18 at 23:57
  • 11
    \$\begingroup\$ I would advise against downvoting this for similarity to the TREE(3) question: Loader's number is so much larger than TREE(3) that new and interesting approaches are required. \$\endgroup\$
    – lirtosiast
    Dec 4 '18 at 1:00
  • 3
    \$\begingroup\$ @fəˈnɛtɪk Well, printing Loader's number + 1 is still interesting from a code golf perspective (for example, can you beat the original 512 bytes?) There are also some natural generalizations of loader's number that might be easier to implement (for example, using ZFC instead of CoC). Also, Greedy clique sequences or finite promise games could be used. \$\endgroup\$
    – PyRulez
    Dec 4 '18 at 3:24
  • 3
    \$\begingroup\$ Unfortunately, as I don't understand the construction of Loader's number and there does not seem to be known upper bounds in terms of the fast growing hierarchy, I cannot give any good answers here. I believe that most answers will be either extensions of Loader's number or things such as the greedy clique sequences and finite promise games... \$\endgroup\$ Dec 4 '18 at 12:33
12
\$\begingroup\$

JavaScript, D6(9) (508 501 495 492 487 485 481 478 456 452 bytes)

_='P6x-~x<<c,Z6r=x&1?0:1+Z@/2.L6x/2>>Z@.S=;t,f=Ft.x=rKf-2?f>2?f-v?t-(f>v)*c:y:Cf,CH(v+2E,#y.Z@BB:A(H;Z@B.A6L@)-1?5<<PM):GE,Z(rND=M=0,O7,Q14K_=@&&D@-1.!1B?(d=FFD@B.f=Fr.x=Fr.c-r||(Fu)||Fr)-f||!QG,d,r.OA(t,dNfIdE.O#t.Q#uB.c&&!OC~u&2|!Q1<<CFc.uNCFc.tNc=r.uItE.Q#t.O9.DM,t,uB:CCt,Cu,PMB._.JJJ9BBB!@>>=1)%2&&(#G-8,13,N)..),6=MK;(vE,y,HS;L@NS@(xB))I/2&!c=CCP(M@EE,cFL(GS(4,4JD(D(K)=>Ot=Qu=';for($ of'QOKJGFEMCIB@H;6.N#!')with(_.split($))_=join(pop());eval(_)

This is an encoded code.

_='P6x-~x<<c,Z6r=x&1?0:1+Z@/2.L6x/2>>Z@.S=;t,f=Ft.x=rKf-2?f>2?f-v?t-(f>v)*c:y:Cf,CH(v+2E,#y.Z@BB:A(H;Z@B.A6L@)-1?5<<PM):GE,Z(rND=M=0,O7,Q14K_=@&&D@-1.!1B?(d=FFD@B.f=Fr.x=Fr.c-r||(Fu)||Fr)-f||!QG,d,r.OA(t,dNfIdE.O#t.Q#uB.c&&!OC~u&2|!Q1<<CFc.uNCFc.tNc=r.uItE.Q#t.O9.DM,t,uB:CCt,Cu,PMB._.JJJ9BBB!@>>=1)%2&&(#G-8,13,N)..),6=MK;(vE,y,HS;L@NS@(xB))I/2&!c=CCP(M@EE,cFL(GS(4,4JD(D(K)=>Ot=Qu='; //encoded code
for($ of'QOKJGFEMCIB@H;6.N#!')with(_.split($))_=join(pop()); //decoding
eval(_) //Evaluation of the string

Decoded code:

P=(x,c)=>x-~x<<c,Z=(x,c)=>r=x&1?0:1+Z(x/2),L=(x,c)=>x/2>>Z(x),S=(v,c,y,t,f=L(t),x=r)=>f-2?f>2?f-v?t-(f>v)*c:y:P(f,P(S(v,c,y,L(x)),S(v+2,c,S(4,4-8,13,y),Z(x)))):A(S(v,c,y,L(x)),S(v,c,y,Z(x))),A=(x,c)=>L(x)-1?5<<P(x,c):S(4,4,c,Z(r)),D=(x,c=0,t=7,u=14)=>_=(x&&D(x-1),(x>>=1)%2&&(1))?(d=L(L(D(x))),f=L(r),x=L(r),c-r||(L(u)||L(r)-f||(x>>=1)%2&&(u=S(4,4,d,r),t=A(t,d)),f/2&(x>>=1)%2&&(c=P(d,c),t=S(4,4-8,13,t),u=S(4,4-8,13,u))),c&&(x>>=1)%2&&(t=P(~u&2|(x>>=1)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r),u/2&(x>>=1)%2&&(c=P(t,c),u=S(4,4-8,13,t),t=9),D(x,c,t,u)):P(P(t,P(u,P(x,c))),_),D(D(D(D(D(D(9))))))
// We also have _ equal to the code itself.

The logic is the same as the original loader.c, but few non-critical modifications are made to compress the code better.

In this, it is assumed to be:

  • Infinite call stack
  • Infinite memory
  • Infinite precision Number
  • Infinite magnitude Number
  • Bitshift and bitwise operators work on infinite bit integers instead of 53 bits. Bitwise negation still negates the sign bit.

Encoding/Decoding algorithm:

The encoding is done as follows:

  • Take a repeated string, call it S.
  • Replace all S in the code to a key K.
  • Put K and S at the end.
  • Make a list of keys, and also put decoding algorithm so the code actually runs.

The decoding algorithm:

  • Take list of keys.
  • Take the earliest key K.
  • Split the string for each K.
  • Since last of the array is what to replace K S, pop it, and replace all K by joining the array with the popped value S.

The compression was done with this code.

(d=String.fromCharCode)((c=a.charCodeAt())>>8)+d(c&255)).join``.slice(1)) ``` This code will take the 16bit string as a, converts it to 8bit string with same binary(BE), and `eval` it. The decoded code is the encoded code above. -->

Proof that D6(9)>D5(99)

For this, we would compare D(0) and 99. We find that D(0) is equal to 8646911284551352321 (note that in a normal environment without modifications we won't get a correct result because the higher bits are truncated). So, D(0)>99, and since D is strictly increasing, D6(9)>D6(0)>D5(99).

  • 508B->501B, -7B
    • -1B for... I don't know why. I did change D(D(D(D(D(99))))) to D(D(D(D(D(D(9)))))). Also that shuffled the letters.
    • -6B for re-adding &&(1) for D(x)'s loop condition.
  • 501B->495B, -6B
    • Fixed most /2s to >>1s because Number
    • 6 bytes saved from somewhere
    • You can see my attempt in this update here
  • 495->492B, -3B
    • By changing the decoder from for...in to for...of.
  • 492->487B, -5B
    • Removing unnecessary assignments
    • Changing argument names
  • 487->485B, -2B
    • 1 byte from using eval for D, removing return.
    • 1 byte compression combining the closing parentheses to a comma.
  • 485->481B, -4B
    • By compressing different substrings.
  • 481->478B, -3B
    • Removed unnecessary variable assignment.
  • 478->456B, -22B
    • You can find me posting updates at Googology Server! (Discord).
    • 2 bytes from changing from D6(9) to D6(0).
    • 1 byte from making D recursive instead of using a loop.
    • 7 bytes from making f and d in D global and not declaring them. It works since they are reassigned every time going through the loop, and D is not called between the assignment and the next iteration.
    • 2 bytes from removing assignment to r. They will be assigned before use.
    • 1 byte from removing an unnecessary assignment corresponding here in the original code. It no longer saved bytes.
    • 1 byte from fixing a typo. I still don't know how it appeared.
    • 2 bytes from swapping the second and the third variable of S. I checked and it should work fine.
    • 1 byte from changing instances of S(4,-4,13, to S(4,4-8,13,.
    • 2 bytes from adding unused variables y to Z and L.
    • 1 byte from changing Z.
    • 2 bytes from reusing _ as the accumulator. It starts out as a String containing the decoded code, and in such a case, it acts as 0 in bitwise operators. Also changed back to D6(9) for good measure.
  • 456->452B -4B
    • Changed the 1-argument and 2-arguments functions' argument names to (x,c).
\$\endgroup\$
0
3
\$\begingroup\$

Python, 498 bytes, ???

I don't know how large this program would get.

Okay, I've had a few failed attempts on this, but I think I've got it this time. First, the code:

from itertools import product as X
C=[1,0]
V=[9]
r=range
L=list
def R(n):
    C[0]=1
    while C[0]:
        C[0]=0
        for m in r(V[0]):P(m,n)
        if(C[0]<1)+(C[1]<len(V)):P(C[1],n,1)
    return sum(V)
def P(m,n,B=0,T=0):
    if m==len(V):V.append(0)
    k=m+n;c=r(k)
    for M in X(*[L(X(*[L(X(c,c,[-1,0,1]))]*k))]*k):
        t={};u=p=s=d=1
        while d:
            s,c,d=M[s][t.get(p,0)];t[p]=c;p+=d;u+=1
            if u>sum(V):u=d=0
        T+=u
    if T>V[m]:C[0]=V[m]=T;C[1]=min(C[1],m+1)
    if B>C[0]:V[m]+=1;P(m,n,1)
z=9**9
exec("z=R(z);"*R(z))
print(z)

Explanation:

This function simulates all Turing machines with n states and n colours for a number of steps (initially 9), then sums the number of steps that it took for any machine that halted to halt, storing that value as the number of steps to take on the next iteration. It keeps doing this until it reaches a steady state.

We don't just look at machines that have n states and colours, but also n+1, n+2, up to n+V[0], where V[0] is the sum of the halting times for the machines with n states and colours.

So far, I've just described a function which is polynomial at best. Notably, it grows slower than the busy beaver function on these Turing machines. Thus, we can be confident that there is at least one machine of size n which halts but we have not yet found. So we search for that one (this function is undefined on inputs which are too small).

Once we find it, we continue on as we were. We'll reach another steady state. This time, we can't be confident that there is another halting Turing machine of size n, but as BB(n+1)>F(BB(n)) for any reasonable polynomial function F (which this is), we can be confident that there is a halting Turing machine of size n+1 which we have not found. If we then find a halting machine of size n, we know that we can perform this step on n+1 again.

We repeat this process until we've attempted this on every size of machine we're looking at (from n to n+V[0]), and thus can no longer be confident that there is a machine that halts of those sizes that we have not seen.

While this number is certainly less than BB(n), I'm not sure how one would go about determining just how big it is. The guarantee that it halts is basically "BB(n) grows much faster than this does". I'm fairly confident that's a safe assumption for values of R(n) greater than, say, R(5).

Here's a less golfed version with comments:

from itertools import product as X
 # C[0] is 1 or 0 representing a change, so keep looping
 # C[1] is the next machine that needs to search.
C=[1,0]
 # V[x] is the total steps taken by the machine with n+x colours and states
V=[9]
def R(n):
    while C[0]:
        C[0]=0
        # Run each set of machines sum(V) steps.
        for m in range(V[0]):P(m,n)
        # Run machine set C[1] sum(V) steps, then run it until one more machine stops.
        if C[0]<1 and C[1]<len(V):P(C[1],n,1)
    return sum(V)
 # Run one set of machines with m+n colours and states.
def P(m,n,B=0):
    if m==len(V):V.append(0)
    # Start our total at 0
    T=0
    # For each machine in the set...
    for M in G(m+n):
        # Step count u starts at 0
        # The tape t starts empty
        # Position p starts at 1
        # State s starts at 1
        # Direction d starts at 1.  These are all 1 because it's shorter and we use d=0 as break
        t={};u=p=s=d=1
        while d:
            s,c,d=M[s][t.get(p,0)];t[p]=c;p+=d;u+=1
            if u>sum(V):u=d=0
        T+=u
    # If the total is greater than the last time we ran this set, increase it and note there's been a change
    if T>V[m]:
        C[0]=V[m]=T
        if m<C[1]:C[1]=m+1
    # If we're running it until there's a change, increment V[m] and try again.
    if B>C[0]:V[m]+=1;P(m,n,1)
 # Generate all the machines of appropriate size.
def G(k):
    L=list
    # List of colours
    c=range(k)
    # List of options for a single state/colour combination - new state, colour written, direction moved (0 being halt)
    O=L(X(c,c,[-1,0,1]))
    # List of options for one state
    S=L(X(*[O]*k))
    # List of options for all states
    return L(X(*[S]*k))
r=9**9
for i in range(R(r)):
    # Reset C[0], as we need to be able to run again.  C[1] will get reset in P().
    C[0]=1;r=R(r)
print(r)

Actually, it occurs to me that there's no reason why (in principle) we can know that R(n) < BB(n) (when BB(n) is defined to be on Turing machines with n colours and states). Determining exactly how big R(n) is is related to a limited version of the halting problem, as it isn't guaranteed that $$BB(n)*2^{n*2^{3n^2}}<BB(n+1)$$ That's the limit on how quickly R(n) grows without the "look for the next terminating machine" step. I think it's a pretty safe assumption, though, that it's true with n>5 or so.

while we can know that R(n) halts on big enough inputs, it's certainly possible that the result is in every case larger than BB(n). Proving such (if true) would be equivalent to the halting problem, of course.

\$\endgroup\$
5
  • \$\begingroup\$ I'm looking at the golfed code and some stuff isn't making sense. if(C[0]sum(V): looks like a typo -- it's not syntactically valid. P and T are undefined. L and X are defined but not used. \$\endgroup\$
    – xnor
    Feb 14 '20 at 20:09
  • \$\begingroup\$ @xnor There was an edit fixing formatting; it caused a bunch of stuff to disappear because < was causing issues. I've corrected it now. \$\endgroup\$ Feb 14 '20 at 20:15
  • 1
    \$\begingroup\$ I tried to fix it. Let me know if there's trouble. Code blocks (with Ctrl+K) respect code formatting better than code tags. \$\endgroup\$
    – xnor
    Feb 14 '20 at 20:24
  • 1
    \$\begingroup\$ It looks like z=9e9 ends up in a range, which only accepts integers, not integer-valued floats. So I think you need something like 9**9 or whatever is big enough. \$\endgroup\$
    – xnor
    Feb 14 '20 at 20:26
  • \$\begingroup\$ @xnor and Spitemaster mea culpa. I just put in the tags and didn't even check the output. Lazy editing on a Friday afternoon. That'll teach me to ship code on a Friday. \$\endgroup\$
    – Giuseppe
    Feb 17 '20 at 20:53
2
\$\begingroup\$

Ruby, D6(9) (553 544 535 516 511 507 bytes)

_='a=r=0;P"x-~x<<y};Z"r=x%2B1?0M1+J/2FL"x/2>>JFS=->vEt{f=L(t);x=r;fB2?A*EJ6Mf>2?fBv ?yMf>v ?t-cMtM@f,P*+2,#y8c,J6FA"Cx]B1?Ky,4,Z[r]]M5<<@x,yFD"f=d=c=0;t=7;O14;while[xIHx-18.>0][1];d=CCHx6;f=N;x=N;cBr&&[Cu]B0&&NBf&&.I[OKd,4,rQA[t,d]8fGd,cQ#t8O#u6;cI.&&[t=@~u&2|.I(O1<<@Cc8u]),@Cc8t]8c=r];uGt,c8O#tQ9];end;a=@@t,@u,@x,c6,aF$><<HHHHHH966"=->x,y=0{#K13,-4,*[S[vECx]8S[v.(x/=2)%26]]]8],@P[B==CL[E,y,c,F]};G/2&.I[c=@HD[IB0||JZ[xKS[4,M: NCr]Ou=Q8t=';'QONMKJIHGFECB@86.*#"'.each_char{|y|*_,y=_.split y;_=_*y};eval _

This is an encoded code. Extracted:

a=r=0;P=->x,y=0{x-~x<<y};Z=->x,y=0{r=x%2==1?0: 1+Z[x/2]};L=->x,y=0{x/2>>Z[x]};S=->v,y,c,t{f=L(t);x=r;f==2?A[S[v,y,c,L[x]],S[v,y,c,Z[x]]]: f>2?f==v ?y: f>v ?t-c: t: P[f,P[S[v,y,c,L[x]],S[v+2,S[4,13,-4,y],c,Z[x]]]]};A=->x,y=0{L[x]==1?S[4,y,4,Z[r]]: 5<<P[x,y]};D=->x,y=0{f=d=c=0;t=7;u=14;while[x==0||D[x-1],(x/=2)%2>0][1];d=L[L[D[x]]];f=L[r];x=L[r];c==r&&[L[u]==0&&L[r]==f&&(x/=2)%2==0||[u=S[4,d,4,r],t=A[t,d]],f/2&(x/=2)%2==0||[c=P[d,c],t=S[4,13,-4,t],u=S[4,13,-4,u]]];c==0||(x/=2)%2&&[t=P[~u&2|(x/=2)%2==0||(u=1<<P[L[c],u]),P[L[c],t]],c=r];u/2&(x/=2)%2==0||[c=P[t,c],u=S[4,13,-4,t],t=9];end;a=P[P[t,P[u,P[x,c]]],a]};$><<D[D[D[D[D[D[9]]]]]]

This code is Loader's Number with D6(9) instead.

In this, it is assumed to be:

  • Infinite call stack
  • Infinite memory

This is basically a port of my JavaScript answer and Python 3 answer. For more details, check those.

The compression was done with this.

I am a beginner at Ruby, so maybe under 512 is possible, but I doubt it.

  • 553->544B, -9B
    • Added 3 bytes from fixing a formatting error.
    • 5 bytes from removing an unused print.
    • 4 bytes from changing expression t-(f>v ?1: 0)*c to f>v ?t-c: t
    • 1 byte from removing an unnecessary assignment to t.
    • 2 bytes from removing an assignment to r.
  • 544->535B, -9B
    • Improved the decoder.
  • 535->516B, -19B
    • 17 bytes from changing functions to lambda expressions.
    • 1 byte each from removing parenthesis from split and eval.
    • Thanks @Dom Hastings!
  • 516->511B, -5B
    • Use a and r declared globally, instead of $a and $a.
  • 511->507B, -4B
    • Change all 1 and 2 argument functions' arguments to x,y=0.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Hey, nice answer! I think you can save a few bytes dropping parens from eval, split, etc, and in the compressed string any calls that are before a ; or ] could probably have parens removed too. Even D D D D D D 9 should work. Not sure if that'll help get closer to 512... \$\endgroup\$ Jul 29 at 8:01
1
\$\begingroup\$

Python 3, D^6(9) (608 600 599 597 591 583 573 bytes)

_="a=06PJ$x-~x<<c6ZJr=0'E?1+TKQ$r6LJ$xK+T)6@t!YtUr#$A([@TC)'f==2?If,I[S(v+2R,/yUTCC'f<2?t-(f>v)*c'f-v?y6AJ$5<<PB)'Fx)-1?MR,Z(rC6DB=0,t=7,X14!Gx:Nx-1Q.G~EV a=IIt,Iu,PBCUaQ $a#d,YFNxCUFrUFrQGc-rV'not(Fu)or(Fr)-fCH'E:XM,d,rOA(t,dQ'fKH'WdRO/t);X/uQGcV .'EH q=~u&2|E# 'q:X1<<IFuUuQ  tR=Iu'q?q,IFcUtC,r#.GuK&WtR);X/tO9#$DB,t,u)\nprint(NNNNNN9CCC)!)Vglobal r,a##\n $return ' G.x=xK#/M-8,13,6\ndef ? else @S(vR,y,B(xRC))Ex%2FL(Gif HV  . IP(JB=0!K>>1MS(4,4ND(O);t=Q)#R,cTZ(xU),V:#WE:c=IXu=Yf,x=F[@FxC,"
for Y in"[YXWVUTRQONMKJIHGFECB@?6/.'$#!":_=_.split(Y);_=_.pop().join(_)
exec(_)

This is an encoded code. Extracted:

a=0
def P(x,c=0):
 global r,a
 return x-~x<<c
def Z(x,c=0):
 global r,a
 r=0 if x%2 else 1+Z(x>>1)
 return r
def L(x,c=0):
 global r,a
 return x>>1+Z(x)
def S(v,c,y,t):
 global r,a
 f,x=L(t),r
 return A(S(v,c,y,L(x)),S(v,c,y,Z(x))) if f==2 else P(f,P(S(v,c,y,L(x)),S(v+2,c,S(4,4-8,13,y),Z(x)))) if f<2 else t-(f>v)*c if f-v else y
def A(x,c=0):
 global r,a
 return 5<<P(x,c) if L(x)-1 else S(4,4,c,Z(r))
def D(x,c=0,t=7,u=14):
 global r,a
 if x:D(x-1)
 x=x>>1
 if ~x%2:
  a=P(P(t,P(u,P(x,c))),a)
  return a
 d,f,x=L(L(D(x))),L(r),L(r)
 if c-r:
  if not(L(u)or(L(r)-f)):
   x=x>>1
   if x%2:u=S(4,4,d,r);t=A(t,d)
  if f>>1:
   x=x>>1
   if x%2:c=P(d,c);t=S(4,4-8,13,t);u=S(4,4-8,13,u)
 if c:
  x=x>>1
  if x%2:
   x=x>>1
   q=~u&2|x%2
   if q:u=1<<P(L(u),u)
   t,c=P(u if q else q,P(L(c),t)),r
 x=x>>1
 if u>>1&x%2:c=P(t,c);u=S(4,4-8,13,t);t=9
 return D(x,c,t,u)
print(D(D(D(D(D(D(9)))))))

In this, it is assumed to be:

  • Infinite call stack
  • Infinite memory

This is basically a port of my JavaScript answer. For more details, check that one.

The compression was done with this.

I am not very knowledgeable in Python, so there are certainly places to save bytes. I think sub-600 is possible. sub-600 has been proven.

  • 608->600B, -8B
    • Grouped some assignments
    • Reversed conditions of S to reduce parenthesis
  • 600->599B, -1B
    • Changing u/2 in the third last line of the definition of D to u>>1, saving a byte from compressing it to a character with other >>1s.
  • 599->597B, -2B
    • 2 bytes from removing assignment to r.
  • 597->591B, -6B
    • Made D recursive.
    • Removed the unnecessary assignments to d, f, and c. Making D recursive allows this to be completely removed and save more bytes whereas keeping it in a loop would have still needed an assignment to c.
  • 591->583B, -8B
    • Changed the 1-argument and 2-arguments functions' arguments to (x,c=0).
    • Added global r,a to every function.
    • Swapped the second and the third of S.
    • Changed the instances of S(4,-4,13, to S(4,4-8,13,.
    • Fixed the compression algorithm (specifically displaying) so it actually works now.
  • 583->573B, -10B
    • Replaces q and u with u if q else q and that somehow saved 10 bytes.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.