Largest total computable function competition

[Moosey]

Wait, ZFC can't prove itself?

Have you heard of godel's incompleteness theorems?
One says no system can prove itself sound

EDIT:
X-post:

The decord (decreasing ordinal) sequence:

start with an ordinal c as term 1.
Rules:
Iff term n is 0: stop
Else:
Iff term n (call it a) is a limit ord, whose minimum "term" (eg. in w^w + w^4 + w2 = w^w + w^4 + w + w, the minimum term is w) is b, and for whom the rest of the terms of a are called r:
term n+1 = r+b[n] + b[n-1] + b[n-2] ... b[1],
Else:
Term n+1 = a-1

Demo:

Code: Select all

w+1
w
3
2
1
0

Code: Select all

w^w+1
w^w
w^2+w
w^2+6
w^2+5
w^2+4
w^2+3
w^2+2
w^2+1
w^2 (10th term)
w55
w54+66
...
w54 (78th term)
w53+3081
...
w53 (3160th term)
...

Obviously this leads to a new function:
the term in the decord sequence for the ordinal a at which it becomes zero = dco(a) (decord)
dco(w+1) = 6, and dco(w^w+1) is ~tri^53(3160), give or take an iteration or two, where tri(n) = the nth triangular number. This suggests a reasonable bound of dco(w^w+1) << 3160^106 (though not in a googolplex-vs-g_64 kind of <<)

Since a[n] < a for all finite n, all decord sequences strictly decrease over time. Thus, dco(a) is finite for all a

Obviously, this leads to new fast growing function: dscrd(n) (yes, that's the word discord without vowels since the definition of discord is general chaos, and that's what this decord stuff is) = max{dco(ord(0),dco(ord(1),dco(ord(2),dco(ord(3),dco(ord(4),...dco(ord(n)}


dscrd(0) = 1
dscrd(1) = dco(1) = len{1,0} = 2
dscrd(2) = dco(w) = len{w,1,0} = 3
dscrd(3) = 3 (two decord sequences, the one starting with w and the one starting with 2, tie for this)
dscrd(4) = dco(w^w) (is max of sequence) = len{w^w,w,3,2,1,0} = 6
dscrd(5) = 6 (w+1's sequence ties with w^w's though)
dscrd(6) = 6 (another w+1, also second time dscrd(n) = n. its growth is pretty erratic.)
dscrd(7) = 6 (ord(7) is a pathetic 3)
dscrd(8) = 6 (we get w^2, whose sequence = {w^2,w,3,2,1,0}) This is getting boring, but don't worry about that-- it gets good for 9:
dscrd(9) = len({w^w+1,w^w,w^2+w,w^2+6,...}) -- hey, this is familiar-- = approx. tri^53(3160), where tri(n) = the nth triangular number. Where the crumbs did that come from?!?
dscrd(10) = dscrd(9) (dco(ord(10)) fails to exceed that of 9)
dscrd(11) = dscrd(9) (dco(ord(11)) fails to exceed that of 9)
dscrd(12) = dscrd(9) (exactly equal to dscrd(9) -- ord(12) = ord(9) = w^w+1)
dscrd(13) = dscrd(9) (dco(ord(13)) = dco(ord(11)) fails to exceed that of 9 or 12)
dscrd(14) = dscrd(9) (dco(ord(14)) = dco(ord(13)) = dco(ord(11)) fails to exceed that of 9 or 12)
dscrd(15) = dscrd(9) (dco(ord(15)) is a measly 5)
dscrd(16) = dscrd(9) (unfortunately, len({w^w^w, w^w, w^2+w...}) is exactly = len({w^w+1,w^w,w^2+w,w^2+6,...} since they converge immediately))
dscrd(17) = dscrd(9) (len({w^2+1,w^2,w3,w2+6,...}) is pretty much the largest thing so far that does not converge on len{w^w+1,w^w...}, but does not exceed it)
dscrd(18) = len({w^w+w, w^w+1, w^w,w^3+w^2+w, w^3+w^2+10...}), which exceeds dscrd(9) by an extreme amount.
dscrd(19) and dscrd(20) = dscrd(18) since dco(ord(19)) and dco(ord(20)) = dco(ord(18)) and hence don't exceed it.

[PkmnQ]

Hey, remember œ and œS?
I just thought, “iterations”.
œS_n(x) =
S(x) if n=0
œ(œS_n-1,x,x)

Let me just remind myself before I try this.

Code: Select all

œ(F, x, y) = {
    F(y) when x = 0
    F^(y!)(œ(F^(y!*x), x-1, F(x))) otherwise
}

Code: Select all

oes(n, x, y) = {
    y + n when x = 0
    oes(n*y!*x, x-1, x+n) + y! otherwise
}

oes(x) = oes(x, x)
oes(x, y) = oes(1, x, y)

Ok, let’s see now.

Code: Select all

œS_2(1)
œ(œs,1,1)
œs(œ(œs,0,œs(1)))
œs(œ(œs,0,4))
œs(œs(4))
œs(69300*(99!*34652! + 1) + 34652! + 99! + 145) which i am not going to calculate

Code: Select all

œS_2(2)
œ(œs,2,2)
œs(œs(œ(œs^4,1,œs(2))))
œs(œs(œ(œs^4,1,37)))

Code: Select all

œS_3(1)
œ(œS_2,1,1)
œS_2(œ(œS_2,0,œs(69300*(99!*34652!+1)+34652!+99!+145)))

[testitemqlstudop]

This function is at least f_w^w, but I could be wrong.

Code: Select all

§2(a, b, c, d) =
a^c+2                                                                                b = 0
§2(a, b-1, c, a)                                                                     d = 0
§2(§2(§2(a+1, b-1, c, a+1), b, c, d-1), b-1, c, §2(§2(a+1, b-1, c, a+1), b, c, d-1)) otherwise

For people screaming "salad number", it's actually a compression of a two-function system.

Code: Select all

§(a, b, c) =
a^c+2 when b = 0
lay(a, b, c, a) otherwise

lay(a, b, c, l) =
§(a, b-1, c), l = 0
§(lay(§(a+1, b-1, c), b, c, l-1), b-1, c) otherwise

[Moosey]

What is the growth rate of dco(Γ_0 +n)?
And is dco(Γ_0+1) the largest value I have coined so far? Or am I overestimating my ability to approximate googologisms?
Can anyone make up some bounds on dco(Γ_0+1)?
And am I right in saying that as n -> infinity, dco(Γ_0+n) < f_Γ_0(n)?


EDIT:
Since Goodstein sequences are equivalent to the length of "decay chains" starting at values < e_0, I guess dco(Γ_0+n) >> goodstein(n) for large enough n (since even if the decay "sequences" were less powerful you still have a whole lot of padding) = ~f_e_0(n), which would mean dco(Γ_0+n) > f_e_0(n)

Am I right to think this way?
If it is > f_e_0(n), are there more (significantly larger) ordinals for whom f_a(n) is exceeded by dco(Γ_0+n)?

[PkmnQ]

Code: Select all

mul(n,k,x) =
mul(n-1,kn,kx) if n > 0
kx if n = 0

Code: Select all

smul(n,x)
mul(smul(n-1,x),n,x) if n>1
mul(2,2,x) if n=1

Code: Select all

ssmul_n(x)
smul(x,x) if n=0
smul(ssmul_n[x](x),x) if n a limit ord
ssmul_n-1(x+1) if n not a limit ord

This probably classifies as salad number, but I don’t care.

Code: Select all

ssmul_w(1)
smul(smul(2,2),1)
smul(mul(smul(1,2),2,2),1)
smul(mul(mul(2,2,2),2,2),1)
smul(mul(mul(1,4,4),2,2),1)
smul(mul(mul(0,4,16),2,2),1)
smul(mul(64,2,2),1) which will be annoying to calculate

Code: Select all

ssmul_w^2+1(1)
ssmul_w^2(2)
smul(ssmul_w2(2),2)
smul(smul(ssmul_4(2),2),2)
smul(smul(smul(6,6),2),2)
smul(smul(mul(smul(5,6),6,6),2),2)
smul(smul(mul(mul(smul(4,6),5,6),6,6),2),2)
smul(smul(mul(mul(mul(smul(3,6),4,6),5,6),6,6),2),2)
smul(smul(mul(mul(mul(mul(smul(2,6),3,6),4,6),5,6),6,6),2),2)
smul(smul(mul(mul(mul(mul(mul(smul(1,6),2,6),3,6),4,6),5,6),6,6),2),2)
smul(smul(mul(mul(mul(mul(mul(mul(2,2,6),2,6),3,6),4,6),5,6),6,6),2),2)
smul(smul(mul(mul(mul(mul(mul(mul(1,4,12),2,6),3,6),4,6),5,6),6,6),2),2)
smul(smul(mul(mul(mul(mul(mul(mul(0,4,48),2,6),3,6),4,6),5,6),6,6),2),2)
smul(smul(mul(mul(mul(mul(mul(192,2,6),3,6),4,6),5,6),6,6),2),2) which will be very annoying to calculate

[Moosey]

What if I defined an array system that looked like this:

Code: Select all

{a,b,c,...x,y,z} = 1+{a+1,b+1,c+1...x+1,{a,b,c,...x,y,z-1},z-1}, z>1
{a,b,c,...x,y,z} = {a,b,c,...x,y}, z=1
{a,b} = a^b

Code: Select all

{#1[0]#2} = array of {#2} {#1}s (i.e. {{#1},{#1},{#1},{#1},{#1}...{#1}} w/ #2 {#1}s)
{#1[0]#2[0]#3} = array of {#2[0]#3} {#1}'s
{#1[n+1]#2} = {#1[n]#1[n]#1[n]} w/ {#2} #1's (w/similar associativity)
{#1[O]#2} = {#1[{#1}]#2}

(Note: this is not an attempt to exceed beaf; I'm not an idiot)
How large is {10,10,10[O]10,10,10}?

[fluffykitty]

Infinite because the first rule reuses {a,b,c...x,y,z} in the result unmodified

[Moosey]

Infinite because the first rule reuses {a,b,c...x,y,z} in the result unmodified

updated, sorry about the typo!

[fluffykitty]

Probably about f_w2. For more details join the Googology Discord server at discord.gg/V6R4hRJ

[Moosey]

SSCG(n) is at least comparable to LSSCG^n(0), using this very suboptimal method:

Code: Select all

1. 1 to itself
2. 1 - 1
3. 1, 1, 1
4. 1, 1
5. 1
... (SSCG(5) solution using 2s)
... (SSCG(5SSCG(5)-1) solution using 3s)
... etc.
etc.

obviously this is a much better solution:

Code: Select all

1. 1 to itself
2. 1 - 2
... (essentially SSCG(2) where a 1 node to itself is taken)
... (something < SSCG(SSCG(2)) in length, made of 2s and no 1 nodes)
... etc.

This means LSSCG(2) is likely >> SSCG(13)

[Moosey]

A new fgh relative, which I call nh (for new hierarchy).

Using the rules I have compiled for fundamental sequences,

Code: Select all

Rule 1. w[n] = n
  Rule 2. w^(a+1)[n] = (w^a)(n)
  Rule 3. If a is a limit ordinal and is less than e_0, (w^a)[n] = w^(a[n])
  Rule 4. e_0[1] = w
  Rule 5. e_0[n+1] = w^e_0[n]
  Rule 6. All rules after rule 6 have a colon rather than a period after the number
  Rule 7: phi_(a+1)(0)[n] = phi^n_a(0) (which means phi_a(0) iterated n times, not phi^(n_a)(0)), for all a > 0
  Rule 8: phi_(a+1)(b+1)[n] = phi^n_a(phi_(a+1)(b)+1)
  Rule 9: if b is a limit ordinal smaller than phi_a(b) phi_a(b)[n] = phi_a(b[n])
  Rule 10: if a is a limit ordinal smaller than gamma_0, phi_a(0)[n] = phi_(a[n])(0)
  Rule 11: if a is a limit ordinal, phi_a(b+1)[n] = phi_a[n](phi_a(b)+1)
  Rule 12: gamma_(0)[n+1] = phi_(gamma_0[n])(0)
  Rule 13: gamma_(0)[1] = w
  Rule 14: (a+b)[n] = a+(b[n]), a >=b>0, a & b both limit ordinals, a < a+b, b < a+b, where a is the minimal ordinal satisfying these conditions

nh_a(n) =

Code: Select all

n+1, a = 0
nh^g(dco(a+n),a-1,n)_(a-1)(n), a not a lim ord (∃b|(a=b+1))
nh_(a[n])(n)

g(a,b,c)=

Code: Select all

nh^g(a-1,b,c)_b(c), a > 0
c, a = 0

For those curious why I defined two functions, here's part of the original, (probably) equivalent definition:

Code: Select all

x = 126, y = 80, rule = B3/S23
89b9o$86b3o8bo$85bo12bo$83b2o13b2o$82bo$81bo$80bo$79bo$78bo$77bo$76bo$
76bo$75bo$74bo$73bo$73bo$38b2o2b3ob3o2bo2bo3bo2b3obo6bo$38bobobo3bobob
o2bobob3obobo2bo5bo$38b2o2b3ob3o2bobobo2bo2bobobo5bo$71bo$71bo$69b2o$
45bo22bo30b3obobo12bob3obo$45b4o19bo30bobob3o11bo2bobo2bo$46bob3o16bo
31bobobobo12bobobobo$46bo4b4o11bo41bo6bo$46bo8b11o41bobob3obo$47bo59bo
bo5bo$47bo$47bo40b3obobo12bob3obo$47bo40bobob3o11bo2bobo2bo$47bo40bobo
bobo12bobobobo$47bo49bo6bo$47bo48bobob3obo$47bo48bobo5bo$47bo$47bo$46b
o$46bo$46bo$45bo$44bo$44bo$42b2o$40b2o49bo$38b2o$36b2o51bo$33b3o$30b3o
54bo$28b2o$27bo$25b2o$25bo$24bo36b3obobo12bob3obo$23bo37bobob3o11bo2bo
bo2bo$22bo38bobobobo12bobobobo$22bo47bo6bo$22bo46bobob3obo$22bo46bobo
5bo$22bo$22bo27b3obobo12bob3obo$23bo26bobob3o11bo2bobo2bo$23bo26bobobo
bo12bobobobo$23bo35bo6bo$23bo34bobob3obo$24bo33bobo5bo$24bo$39b3obobo
12bob3obo$39bobob3o11bo2bobo2bo$39bobobobo12bobobobo$48bo6bo$47bobob3o
bo$47bobo5bo$77b3o5bo$3obobo5bob3obo3b3o3b3obobo12bob3obo25bob2o2bo2bo
2b3ob2o3bo2bo$obob3o4bo2bobo2bo8bobob3o11bo2bobo2bo22b3ob3obobobo5b3ob
3obo$obobobo5bobobobo3b3o3bobobobo12bobobobo19bo5bob2o2bobobob3ob2o3bo
2bo$9bo27bo6bo28bo3b3o5bo$8bobo25bobob3obo27bo$8bobo25bobo5bo!

[testitemqlstudop]

How do i confirm my user on goowiki, username Testitemqlstudop

can someone please confirm me lol

[Moosey]

How do i confirm my user on goowiki, username Testitemqlstudop

can someone please confirm me lol

I had this problem.
Just confirm yourself via email and wait 4 days. There isn't any other way, unfortunately, to be auto-confirmed.
Will your profile picture be the X3VI thing like your one on the forums?

[testitemqlstudop]

Just confirm yourself via email and wait 4 days. There isn't any other way, unfortunately, to be auto-confirmed.

Awww ok

Will your profile picture be the X3VI thing like your one on the forums?

Yes (as soon as I figure out how to upload gifs), and also how the flip did you recognize that as X3VI?

[testitemqlstudop]

So the previous post won't be off topic, i made a notation. yay

Code: Select all

®(a, b, c) = {
a^c, c = 0
®(®(a+1, b+1, c-1), ®(a+1, b+1, c-1), c-1), otherwise
}

®(a, b, ø) = {
37, a = 0 and b = 0
®(a-1, a-1, ®(a-1, a-1, ø)), b = 0, a != 0
®(b-1, a-1, ®(b-1, b-1, ø)), a = 0, b != 0
®(®(a-1, b, ø), ®(a, b-1, ø), max<a, b>) otherwise
}

[Moosey]

So the previous post won't be off topic, i made a notation. yay

Code: Select all

®(a, b, c) = {
a^c, c = 0
®(®(a+1, b+1, c-1), ®(a+1, b+1, c-1), c-1), otherwise
}

®(a, b, ø) = {
37, a = 0 and b = 0
®(a-1, a-1, ®(a-1, a-1, ø)), b = 0, a != 0
®(b-1, a-1, ®(b-1, b-1, ø)), a = 0, b != 0
®(®(a-1, b, ø), ®(a, b-1, ø), max<a, b>) otherwise
}

The typo is indeed a great enemy of googologists.
I think you mean, in the first part

Code: Select all

®(a, b, c) = {
a^b, c = 0
®(®(a+1, b+1, c-1), ®(a+1, b+1, c-1), c-1), otherwise
}

Also, what is the definition of ø?
Are ®(a, b, ø) and ®(a, b, c) supposed to be two different functions?
If so, please change the symbol because it will be impossible to tell ®(1,2,3) from ®(1,2,3).

how the flip did you recognize that as X3VI?

It looked like it had the X3VI ship

[testitemqlstudop]

ø is intended to be a generic symbol. Pretend it's w

[Moosey]

ø is intended to be a generic symbol. Pretend it's w

Oh, so ø is shorthand for a limit ordinal.
That's a good notation

[Moosey]

Bump

Just confirm yourself via email and wait 4 days. There isn't any other way, unfortunately, to be auto-confirmed.

Awww ok

You should be ready to edit soon (by tomorrow, Oct 19, at the latest)


To make it so that this post isn't off topic:
For what n does dco(Γ_0 +n) exceed G_64?

[testitemqlstudop]

For several reasons of the embedding of fundamental sequences, I don't even think it's total computable at all.

But given that Goodstein(12) > g64, it's plausible that n = 12 will dco(Γ_0 +n) be way larger than g64.
However, in dco it's practically like starting at the peak of the goodstein sequence and then slowly falling, as opposed to starting at the bottom and climbing up.

[Moosey]

For several reasons of the embedding of fundamental sequences, I don't even think it's total computable at all.

Did you figure that out yourself, or are you just taking you-know-who's word for it? But yes, it's *technically* not total computable since TMs can't emulate it too well. So we could go to the total uncomputable thread to discuss it instead.

But given that Goodstein(12) > g64, it's plausible that n = 12 will dco(Γ_0 +n) be way larger than g64.
However, in dco it's practically like starting at the peak of the goodstein sequence and then slowly falling, as opposed to starting at the bottom and climbing up.

1. I think you have the goodstein analogy wrong; goodstein sequence ordinals slowly fall as well.

2. Goodstein sequences may not be a good comparison as no ordinal produced by the goodstein sequence >= e_0, while the supremum of the largest ordinals (I.e. the first ones) in all decord sequences of Γ_0+n for finite in is Γ_0 + w. I'm not saying that dco(Γ_0+n) is f_(Γ_0+w)(n) (probably much closer to just Γ_0 or Γ_0+1), just that it starts decreasing at a much higher value.

For instance, with dco(Γ_0+2), the corresponding sequence looks like this:

Code: Select all

Γ_0+2
Γ_0+1
Γ_0
phi_phi_w(0)(0)+phi_w(0)+w
...
... (dco(phi_w(0)+w+3)-4, > dco(Γ_0+1), terms)
...
phi_phi_w(0)(0)
phi_phi_(dco(phi_w(0)+w+3)+1)(0)(0) + phi_phi_(dco(phi_w(0)+w+3))(0)(0) + ... + phi_z_0(0) + phi_e_0(0)
etc.

Which looks like it may be much larger than G_64 or similar

For relatively small n, dco(Γ_0+n) >> goodstein(n), so dco(Γ_0+12) is definitely >> g_64


EDIT: I think you can edit the wiki now

[testitemqlstudop]

How does the f in the bottom of

https://testitem.github.io/colg/arnot.html

do?

w^w in FGH? or w^w^w in FGH? I think it beats unidimensional BEAF by far

[Moosey]

Is this the correct translation from archaic LaTeX of this, the real number arrow notation?

Code: Select all

a\uparrow^n b=a\uparrow^{n-1}(a\uparrow^n (b-1))\;(b>1) \\

a\uparrow^n b=a^b\;(n>1\wedge0\leq b\leq 1)\\

a\uparrow^n b=a^{1+n(b-1)}\times b^{1-n} (n\leq 1)

[testitemqlstudop]

Heck with ordinals and ill-definedness

https://googology.wikia.org/wiki/User_b ... y_notation

[Moosey]

Heck with ordinals and ill-definedness

https://googology.wikia.org/wiki/User_b ... y_notation

I think that's still has a problem. You're making W(1,1) = W(W(1,1),0) = W(W(1,1)), right? You can't use the same array because otherwise you have issues like this.

Maybe you meant this though

Code: Select all

W({0}) = 0
W({$_0,0}) = W({$_0})
W({$_0,n+1}) = W(W({$_0,n})@(len($_0))#{n})