g | x | w | all
Bytes Lang Time Link
1850Binary Lambda Calculus 1850 bits 231.25 bytes240802T162912ZJohn Tro
nanPython 3191218T175323ZNaruyoko
nanJavaScript190426T034324ZNaruyoko
192Python220415T061356Zbenrg
319Python211120T111732ZBinary19
nanRuby200114T135056ZNaruyoko
498Python200214T164014ZSpitemas

Binary Lambda Calculus: 1850 bits (231.25 bytes):

01000101010110101001000100010001000001000101011000011000000000010111111100011001111111111011001011100001010111000010101111000010000000111100111010011100000000111110000101010101111111111111101111111111011110100000010000010101110010000000101101110110000101011000010110111110111111100001111111111001100000100001111111110011000001000100101010101111111101111111111111111000000111000010101111111111111111110001110111111100001000000010110111011001000001010110111111111110010111011111111111110111111111001011101111111111110111111111000000001010101010111101000000001111000110000010000010000000000101011110000010011111111011111011110011101000001000001001011111100000010000000101101110110010000010101101110010101111111000100101110000011011110111111110010101110111111011110111111100000000000000001010111100000011101111111110011111110111100001111111000010110110111111001011100001011000010101100001011011111101111111100001111111001100000100001100000110110100001010101111011111111111111100000000010000011100000100000001011000101000010110000101011000001000000000011100000110000000000111000001000001000001011000010001101000000110000000010111111101110010101111110111110110100000010101111110000001011101001011011000001100111101100111101000010101010001101000010000000001000100010101111100000000111111001010111111111101111111101100101111000011111110000101101100101011111111111100000011100101111111111111011010011110000000011001111111111111100001100000101111111100111110010101111111111011111111010111111000011100111100001011011011111000011001011111110110011100111101111000000101100000101100000010110000011011001101000001001101100000100101000110100000010000010110000000011011111001011111011110110000111000010110000010110001000010001101000000001011100000000101111100000010101111111111011111011001010111111111011111111011110100000100101100000001111100000110100000011100111010

This is the binary representation of this lambda expression which computes 2^2^2=16 iterations, on starting value 2, of a slightly slower growing derive function which is modeled after this Haskell port of Loader's 643 byte C program.

derive n computes a list of all judgements which can be formed with n rule applications and returns n to the power of the product of all term sizes.

For the first iteration we have derive 2 = 2^27 >> 99.

Loader's Derive does something similar with fewer rule applications but returns a power tower of term sizes instead. Since derive easily constructs power towers, we have derive (derive n) >> D(n), and thus 11 iterations certainly suffice to exceed Loader's number.

Thanks to https://github.com/int-e for some of the final optimizations.

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

_="a=0@PJ$x-~x<<c@ZJr=0'C?1+YxKO$r@LJ$xK+Yx)@SBu!f,d=FuQr#$A(RBYdE)'f==2?If,IR(x+2U,/tQYdEE'f<2?u-(f>x)*c'f-x?t@AJ$5<<P.)'Fx)-1?MU,YrE@D.=0,t=7,u=14!Hx:Nx-1O6H~CXa=IIt,Iu,P.EQaO $a#d,f,x=FFNxEQFrQFrOHc-r:#'not(Fu)or(Fr)-fEG'C:u=M,d,rTA(t,dO'fKG'WdUT/tVuOHcX6'CG q=~u&2|C# 'q:u=1<<IFuQuO  tU=Iu'q?q,IFcQtE,r#6HuK&WtUVtT9#$DBu)\nprint(NNNNNN9EEE)!):#global r,a##\n $return ' H.(xU/M-8,13,6x=xK#? else @\ndef B.,t,Cx%2E))FL(GX 6 Hif IP(J.=0!K>>1MS(4,4ND(O)#Q),RSBFdE,ST);t=U,cV);u=/WC:c=IX:# YZ("
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(x,c,t,u):
 global r,a
 f,d=L(u),r
 return A(S(x,c,t,L(d)),S(x,c,t,Z(d))) if f==2 else P(f,P(S(x,c,t,L(d)),S(x+2,c,S(4,4-8,13,t),Z(d)))) if f<2 else u-(f>x)*c if f-x else t
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:

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.

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

_="P.x-~x<<c,Z.r=x&1?0:1+ZC/2$L.x/2>>ZC$S='u,f=6u$d=rJf-2?f>2?f-x?u-(f>x)*c:t:@f,@EC+2K,IZ(d;;:A(E'Z(d;$A.6x)-1?5<<P!):BK,Z(rMD=!=0,H7,N14J_=C&&DC-1$ 1;?(d=66DC;$f=6r$x=6r$c-r||(6u)||6r)-f|| NB,d,r$HA(t,dMfGdK$HIN#u;$c&& H@~u&2| N1<<@6c$uM@6c$tMc=r$uGtK$NIH9$D'u;:@@t,@u,P!;$_$FFF9;;; C>>=1)%2&&(!CK#B-8,13,$),'!,t,.=!J6L(;))@P(BS(4,4C(xES'6dMSFD(D(G/2& c=@Ht=I#t$J)=>K,cM)$Nu=";for($ of"NMKJIHGFECB@;6.'$#! ")with(_.split($))_=join(pop());eval(_)

This is an encoded code.

_="P.x-~x<<c,Z.r=x&1?0:1+ZC/2$L.x/2>>ZC$S='u,f=6u$d=rJf-2?f>2?f-x?u-(f>x)*c:t:@f,@EC+2K,IZ(d;;:A(E'Z(d;$A.6x)-1?5<<P!):BK,Z(rMD=!=0,H7,N14J_=C&&DC-1$ 1;?(d=66DC;$f=6r$x=6r$c-r||(6u)||6r)-f|| NB,d,r$HA(t,dMfGdK$HIN#u;$c&& H@~u&2| N1<<@6c$uM@6c$tMc=r$uGtK$NIH9$D'u;:@@t,@u,P!;$_$FFF9;;; C>>=1)%2&&(!CK#B-8,13,$),'!,t,.=!J6L(;))@P(BS(4,4C(xES'6dMSFD(D(G/2& c=@Ht=I#t$J)=>K,cM)$Nu="; //encoded code
for($ of"NMKJIHGFECB@;6.'$#! ")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=(x,c,t,u,f=L(u),d=r)=>f-2?f>2?f-x?u-(f>x)*c:t:P(f,P(S(x,c,t,L(d)),S(x+2,c,S(4,4-8,13,t),Z(d)))):A(S(x,c,t,L(d)),S(x,c,t,Z(d))),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:

Encoding/Decoding algorithm:

The encoding is done as follows:

The decoding algorithm:

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

Python, q15(2), 192 bytes

def q(k,c=0,n=0):
 while c*2<1<<k:
  n+=1;*x,=map(s:=lambda b,a=1:s(a,s(b-1,a))if a*b else(a-~b)%c,range(c:=1<<n))
  while x[:c]==x[-c:]:x=x[:c];c>>=1
 return n
print(eval(15*'q('+'2'+')'*15))

See Binary198's answer for the definition of q and an argument that q15(2) is large enough. If the argument is correct, then this is an impressively concise way to beat Loader's number. Unfortunately their implementation is broken.

This is my attempt at reasonably well golfed code that, I think, actually works. At least, it correctly computes values of q up to q(3)=5. (If you want to test that, you should wrap the definition of s in functools.lru_cache(None)(...).) Computing q(4)=9 may be possible, but will need a lot of stack space.

s(b,a) computes row a, column b+1 of the Laver table of size c, using 0...c-1 as the representatives of Z/cZ instead of the usual (for these tables) 1...c. The period-finding code uses the fact that the period can only be a power of 2. Other than that, there are only standard golfing tricks here.

I deliberately computed the same value as Binary198's answer, though it could be made larger at no cost, because I'm not trying to compete on size; I just wanted a working implementation of this interesting function (for some definition of "working").

Python, q^15(2) = q^13(5), 319 bytes

This is my first time submitting a program to code golf, but certainly not my first time implementing or inventing a large number. I probably won't go down in googology history for this. Anyway, here is my program, the explanation comes later:

_="78b/:!if b==1:&(a+1)%c!9&s(8b-1/,s(81///\n7f(a):!m=[]*True:!#for x in range(65536):!##if a(x)==a(x+k): break!##9 pass'p = 4x:f(4y:s(1,y,x))\n7q(a):*p(k)<2^a:'k = $$$$$2...!\n##    $q(q(q('!#k+=1!&k\n&return *!k=0!while .)))))/,c)4lambda 7def 8s(a,9else:"
for Y in"9874/.*&'$#!":_=_.split(Y);_=_.pop().join(_)
exec(_)

I compressed this code using the same tool which Naruyoko used, here. Here is the uncompressed form:

def s(a,b,c):
    if b==1:return (a+1)%c
    else:return s(s(a,b-1,c),s(s(a,1,c),c),c)
def f(a):
    m=[]
    k=0
    while True:
        for x in range(65536):
            if a(x)==a(x+k): break
            else: pass
        k+=1
    return k
p = lambda x:f(lambda y:s(1,y,x))
def q(a):
    k=0
    while p(k)<2^a:
        k+=1
    return k
k = q(q(q(q(q(q(q(q(q(q(q(q(q(q(q(2)))))))))))))))

Explanation

I had a hard time choosing what to use. I was originally planning to implement my LINEAR(k) function, which I might do another time, but I didn't know if it would produce large enough numbers, and it would be hard to implement, so my next choice was greedy clique sequences, but those didn't work either, so I just ended up using Laver tables.

So, how do Laver tables work? Well the size-n Laver table is a binary operator ab, with the following rules: a0=0, a1=a+1 mod n and ab=(a(b-1))(a1) for b>1. p(n) is defined as the period of the function 1a, which is quite slow-growing.

The first few values of p(n) are 1,1,2,4,4,8,8,8,8,16,16,16,16,... Then q(n) is the least integer so that p(q(n)) is greater than or equal to 2^n. This is very fast-growing, and its totality can only be proven in ZFC+I3, so one could approximate it to f_PTO(ZFC+I3)(n) in FGH, although this doesn't work since there is no system of fundamental sequences associated to PTO(ZFC+I3).

The first few values of q(n) are 0,2,3,5,9. q(5) is approximated to Ack(9,Ack(8,Ack(8,255))) using the Ackermann function, and q(6) is believed to be greater than Graham's number!

So, now that we know how Laver tables work, how does my code work? Well, s(a,b,c) denotes the operator ab where n=c, then the function f(a) uses complex while loops to find the period of the given function a.

p is represented by the lambda which returns f(lambda y:s(1,y,x)), i.e. the period of s(1,y,x) where x is the input to p. q then just uses for loops to find the least integer k s.t. p(k) => 2^a.

My code then returns q^13(5), which has been proven to be greater than f_w(f_w+1(5)); note that this was for q^13(1) but q is strictly increasing so this also acts as a lower bound for q^13(5). This lower bound however is a severe understatement, since, as I mentioned earlier, q(n) cannot be proven total in ZFC while f_w(f_w+1(5)) can be by FAR.

Similarly, this code should return a number greater than Loader's number since, although sadly there is no proof, Loader's function is commonly believed to be provably total in ZFC; I do note however that just because a function which is provably total in a stronger theory doesn't mean that it will eventually dominate the one provably total in the weaker theory. It is usually the case though. So, all said, I WIN!!!

Edit: I lose because the code is completely broken and I can't fix it...

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:

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.

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.

GOLFSCORE/176966