Largest total computable function competition

[PkmnQ]

Oh, so if f(x) = 3x+2 then f^3(5) = 161?

[Moosey]

according to Wikipedia, the incredibly unreliable resource™.

The biggest lie perpetrated by humanity (cough. cough. TEACHERS) is that Wikipedia is unreliable. Studies show [citation needed] that for every 1 edit to a page, ten read the page.

Wikipedia has an article explaining that it is not to be used as the only source for research.

Oh, so if f(x) = 3x+2 then f^3(5) = 161?

Yes.

[testitemqlstudop]

Where on the fgh is my function for, say, a function f with growth rate w^2

[Moosey]

Where on the fgh is my function for, say, a function f with growth rate w^2

Are you asking for œ(f_w^2,n,n)?
I'm not sure why I ask since I can't calculate it, but I doubt it's too much higher.

Variant of your function:

Code: Select all

æ(F, x, y, z) = {
    F(y+z) when x = 0
    F(æ(F^x, x-1, æ(F^x, x-1, F(x), z+1))+z, z+1) when y = 0
    æ(F^y, x, y-1, z+1) otherwise
}

Almost at this point, unfortunately:

[salad numbers] are often coined by inexperienced googologists holding the false notions that a more complex definition is a more powerful one.

[PkmnQ]

Where on the fgh is my function for, say, a function f with growth rate w^2

Are you asking for œ(f_w^2,n,n)?
I'm not sure why I ask since I can't calculate it, but I doubt it's too much higher.

Variant of your function:

Code: Select all

æ(F, x, y, z) = {
    F(y+z) when x = 0
    F(æ(F^x, x-1, æ(F^x, x-1, F(x), z+1))+z, z+1) when y = 0
    æ(F^y, x, y-1, z+1) otherwise
}

Almost at this point, unfortunately:

[salad numbers] are often coined by inexperienced googologists holding the false notions that a more complex definition is a more powerful one.

I wonder what æ(S,n,n,n) would be. After all, I did the same with œ.

æ(S,1,1,1) = æ(S,1,0,2) = æ(S,0,æ(S,0,2,3)+2,3) + 1 = æ(S,0,7,3) + 1 = 10 + 1 = 11

æ(S,2,2,2) = æ(S^2,2,0,4) = æ(S^4,1,æ(S^4,1,4,5)+4,5) + 2 = æ(S^4,1,æ(S^96,1,0,9)+4,5) + 2 = æ(S^4,1,æ(S^96,0,97,10)+100,5) + 2 = æ(S^4,1,207,5) + 2 = æ(S^4*(207!),1,0,212) + 2 = æ(S^4*(207!),0,(4*(207!))+1,213) + 4*(207!)+2 = (8*(207!)) + 216

If you recall, œ(S,2,2) was as low as 195.

[testitemqlstudop]

S is f_w, right?

Code: Select all

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

Manually trying to bash out ae(S,4,4):

ae(S,4,4) =
ae(S^4,4,3) =
ae(S^12,4,2) =
ae(S^24,4,1) =
ae(S^24,4,0)=
ae(S^96,3,28)+24=... oh strewth this is not a good idea

Anyways I think this reduction is obvious:

Code: Select all

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

Hence, applying the Y=0, rule, we get

Code: Select all

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

because of applying the rule œ(F^(y!), x, 0)=F^(y!)(œ(F^(y!*x), x-1, F(x))).

Can someone bash further?

I think it is obvious that for f=S then œ is at least as powerful as iterated factorial.

[Moosey]

S is f_w, right?

No, S(n) = n+1
If you're asking about whether œ(S,n,n) or æ(S,n,n,n) are f_w, I don't know. Probably not.

Manually trying to bash out ae(S,4,4):

ae(S,4,4) =
ae(S^4,4,3) =
ae(S^12,4,2) =
ae(S^24,4,1) =
ae(S^24,4,0)=
ae(S^96,3,28)+24=...

Uh, æ has four arguments

æ(S, 4, 4, 4)
= æ(S^4, 4, 3, 5)
= æ(S^12, 4, 2, 6)
= æ(S^24, 4, 0, 8)
= 24 + æ(S^96, 3, æ(S^96, 3, 28, 9))+8, 9)
= 24 + æ(S^96, 3, æ(S^(96*(28!)), 3, 0, 37))+8, 9)
...

[PkmnQ]

Hmm, I wonder if I can make my own function based off of œ. How about for 2-argument functions?

Code: Select all

ø(F, n, x, y) =
F(x,y) [n=0]
F(ø(F^n,n-1,F(n,n),F(n,n)),ø(F^n,n-1,F(n,n),F(n,n))) [x=0, y=0]
F(ø(F^x,n,x-1,F(x,n)),F(ø(F^x,n,x-1,F(x,n)) [y=0]
ø(F^y,n,x,y-1)

[testitemqlstudop]

How do you define F^x for multi-variable functions tho

EDIT: Whoops i meant oe

[PkmnQ]

How do you define F^x for multi-variable functions tho

EDIT: Whoops i meant oe

Oh, theres no actual description yet?
It might be f(f(x, x), f(y, y)) maybe?

[Moosey]

Here's a compacted definition of æ:

Code: Select all

æ(F, x, y, z) = {
    F(y+z) when x = 0
    F(æ(F^x, x-1, æ(F^x, x-1, F(x), z+1))+z, z+1) when y = 0
    æ(F^(y!), x, 0, z+y) otherwise
}

For f(x) = 2^x:
æ(f,2,2,2) =
æ(f^2,2,0,4) =
2^(æ(f^4, 1, æ(f^4, 1, 16, 5))+4, 5)

æ(f^4, 1, 16, 5) =
æ(f^83691159552000,1,0,21)= (you're probably thinking, "holy mustard, where did that come from?")
f^83691159552000(æ(f^83691159552000, 0, æ(f^83691159552000, 0, 2^^83691159552000, 22))+21, 22)

æ(f^83691159552000, 0, 2^^83691159552000, 22)= f^83691159552000(2^^83691159552000+22)

f^83691159552000(æ(f^83691159552000, 0, æ(f^83691159552000, 0, 2^^83691159552000, 22))+21, 22) =
f^83691159552000(æ(f^83691159552000, 0, f^83691159552000(2^^83691159552000+22)+21, 22)=
f^167382319104000(f^83691159552000(2^^83691159552000+22)+43))

2^(æ(f^4, 1, æ(f^4, 1, 16, 5))+4, 5) =

Code: Select all

2^(æ(f^4, 1, f^167382319104000(f^83691159552000(2^^83691159552000+22)+43))+4, 5)

etc, etc

EDIT:
Further compacted æ:

Code: Select all

æ(F, x, y, z) =
    F(y+z), x = 0
    F^(y!)(æ(F^(*y!x), x-1, æ(F^(y!*x), x-1, F^(y!)(x), z+y+1))+z+y, z+y+1), x not = 0

[testitemqlstudop]

Here I have specialized oe for S:

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)

oes(4) = oes(1, 4, 4) = 
         oes(96, 3, 5) + 24 = 
         oes(34650, 2, 99) + 144 = 
         oes(69300*99!, 1, 34652) + 99! + 144 = 
         oes(69300*99!*34652!, 0, 1+69300*99!) + 34652! + 99! + 144 = 
         1 + 69300*99! + 69300*99!*34652! + 34652! + 99! + 144 = 
         69300*(99!*34652! + 1) + 34652! + 99! + 145

... yeah it's pitifully small.

[Moosey]

define tvi(f,n,x,y) (two-var-iteration function) as follows:
tvi(f,n,x,y)=

Code: Select all

f(tvi(f,n-1,x,x),tvi(f,n-1,y,y)), n>1
f(x,y), n=1

tvi is essentially this:

How do you define F^x for multi-variable functions tho

EDIT: Whoops i meant oe

Oh, theres no actual description yet?
It might be f(f(x, x), f(y, y)) maybe?

EDIT:

This morning I created a notation that extends f^a(x). I will use ^. to notate an important part of it so it’s not confused with exponentiation, but think of it is superscript right above something.
It starts like this:
f^1^.a(x) = f^f^f^f^f^f^f^f^f...(x)(x)(x)(x)... with a f’s, all of x
so, where f = +1,
f^1^.5(1)=

Code: Select all

f^f^f^f^f(1)(1)(1)(1)(1)=
f^f^f^f^2(1)(1)(1)(1)
f^f^f^3(1)(1)(1)...
=6

then: f^b^.a(x) = f^b*f^b*f...(x)(x)(x) with a b*f’s.
then, where # represents anything, including a stack: f^#^.b^.a(x)=f^#^.b*f^#^.b*f...(x)(x)(x) with a f^#^.b*’s.
then we have this leap:
f^a|n(x)= f^a^.a^.a^.a^.a ... with n a's.

f^a|n^.#(x)=f^(f^#(a))^.(f^#(a))^.(f^#(a)) ... with n (f^#(a))^. ’s. The initial f, is, of course, still of x.
Then, the next logical extension:
f^a|n|m(x) = f^a|n^.a|n^.a|n... with m a|n ’s.
The logical continuation:
f^a|n|m^.#(x)= f^f^a|n^.#(a)^f^a|n^.#(a)^f^a|n^.#(a)... with f^n|m(a) f’s. The initial f will always be of x of course

Can somebody help me define f^a|b|c|d... with arbitrarily many arguments?
EDIT: nvm, f^a|n|m|#(x)= f^a|n|f^#(m)(x)

Then I can, a la bowers, define f^a||b(x) = f^a|a|a|a|a...(x) with b a’s.

where is S^2||x(1) in the grass-mowing hierarchy? (Probably very low--I mean the fgh of course)
Anyways, now:
f^#||b||c(x) = f^#||(f^b||c(b))(x)

GENERALIZATION TIME YAY
f^a(:b:)c(x) =

Code: Select all

f^a(:b-1:)a(:b-1:)a(x) with c a's, b > 1
f^a|c, b = 1

f^#a(:b:)c(x) =

Code: Select all

f^#a|c(x), b = 1
f^#(:b:)(f^a(:b:)c(a))(x), b > 1

I'm sure that S^3(:x:)3(1) is much higher in the fgh. At least, relatively speaking considering S = the successor function.

S^3(:1:)3(1) = S^3|3(1) = S^3^.3^.3(1) =
S^3^.3*S^3^.3*S^3^.3(1)(1)(1)=

Code: Select all

S^3^.3*S^3^.66(1)(1)

...
Can anyone evaluate it?

[Moosey]

I finally understand the fgh now, and I'm not afraid to use it. First off, a function which eventually dominates f_a(x) for all a < e_0, using the fairly obvious method of... using the fgh
It uses ord, too.

Here's how it works:
ord-fgh(n) =
max{f_ord(1)(n), f_ord(2)(n), f_ord(3)(n)... f_ord(n)(n)}
Provably, at n= 2^^a it suddenly becomes f_w^^a(n), so as long as you have a finite amount of w's in the bottom you can always find an n such that it exceeds f_(the ordinal you're talking about)(n). Therefore it is on par with f_e_0(n), save that it goes much much more slowly than that. But it beats everything below it eventually, so...

The second function (which we'll get to in quite a while) is based on a naïvely created relative of the fgh:

j_n(x) =

Code: Select all

(Technically it was i_n(x) but autocorrect is a REAL PAIN
x+1, n=0
j^(x*(fin(n,x)+1))_n-1(x), n > 0 & not a limit ordinal
j^(fin(n,x)+1)_n[x](x), n a limit ord

Where fin(n,x) is defined thus:
fin(n,x) =

Code: Select all

fin(n-1, x)+1, n not a limit ordinal, n>w
n, n < w 
fin(n[x], x)+1, n a limit ordinal, n>w

Yes, fin(n,x) returns a finite value as long as x is finite

Finally, we can get to my second function on par with f_e_0
Then I defined ordj (and yes, this was originally ordi):
ordj(n) = max{j_ord(1)(n), j_ord(2)(n), ...j_ord(n)(n)}
and of course eventually dominates everything < j_e_0(n) and still is probably on par with f_e_0

[PkmnQ]

I haven’t seen n[x] before.

[Moosey]

I haven’t seen n[x] before.

n[x]
= the xth term of the fundamental sequence of n
so, for instance, w[400] = the 400th term of {0,1,2,3,4,5,6,7,8...} = 400 (at least, this is probably the most formal way to say it-- you could also call it 399 or 401 depending on whether you start your series with entry 0 or 1 or whether omega's sequence includes 0)
and e_0[3] = the 3rd term if {w, w^w, w^w^w, w^w^w^w...} = w^^4 (again, if you start a series with 0 or 1)


So the fgh is actually defined like this:
f_n(x)=

Code: Select all

x+1, n = 0
f^x_(n-1)(x), n > 0, n not a limit ordinal
f_n[x](x), n a limit ordinal

So f_w(x) is really just f_w[x](x)

If you don't know what limit ordinals are, they're distressingly simple. They're just any ordinal you cannot subtract one from. In other words, you aren't adding any finite constants. w, w2, and w^w^w^w +w^3 + w19 are all limit ordinals

[testitemqlstudop]

So the sequence for w^w is [w, w*w, w*w*w, w*w*w*w, ...] and the sequence for w*w is [w, w*2, w*3, w*4, ...]?

Your explanation is better than the one on goowiki

[Moosey]

So the sequence for w^w is [w, w*w, w*w*w, w*w*w*w, ...] and the sequence for w*w is [w, w*2, w*3, w*4, ...]?

Exactly

Your explanation is better than the one on goowiki

Thanks

[Moosey]

(See here)

Code: Select all

ssm_n(x,y)=

x+y, n = 0

ssm_sg(x,n,x,y)(x,y), n a lim ord

ssm_n-1(x,xy) otherwise

define sg(m,n,x,y) =

n[ssm_sg(m-1,n,x)(x,y)], m>0,

x, m less than or = to 0

Does this do what I want?
Also they added new BBcode smilies which totally screwed some of my notation up ( () ())

[Moosey]

Trying to understand BEAF.
the rules of beaf are as follows, right?
(# represents anything in the array)

Code: Select all

{a,1,#} = a
{a,b} = a^b
{#,1} = {#}
{a,b,1,1,1...1,d,#} (any from 1 1 in-between to many many many ones in-between) = {a,b,a,a,a...,{a,b-1,1,1,1...1,d,#},d-1,#}
{a,b,d,#} = {a,{a,b-1,d,#},d-1,#}

[testitemqlstudop]

Yes, that's right for unidimensional arrays.

But I don't get anything above 2d

[BlinkerSpawn]

Yes, that's right for unidimensional arrays.

But I don't get anything above 2d

Let the first non-one entry after b be the "active point" P and the separator before it S.
Decrease S according to the following rules, and call the result S':

Code: Select all

{k #} -> {k-1 #}
{# 1,k #} -> {# b,k-1}
If this separator has another separator at its active point, reduce it the same way.

Then # 1 S P # becomes # 1 S' 1 S' 1 ... 2 S P-1 # with b 1's.

Examples:

Code: Select all

2,3,1{1}2 -> 2,3,1,1,1,2
2,3,1{3}3{4}2 -> 2,3,1{2}1{2}1{2}2{3}2{4}2
2,3,1{1,3}2 -> 2,3,1{3,2}1{3,2}1{3,2}2
2,3,1{1{3}2}2 -> 2,3,1{1{2}1{2}1{2}2}2

This gets you to a,b,1{1{1{1{...}2}2}2}2, which is e0

[testitemqlstudop]

I believe the fastest growing known computable functions are of the following form:

n ↦ The combined running time of all Turing machines (with no input) such that there exists a proof that they halt in second-order PA using fewer than n symbols

FIrst order set theory is much stronger, and you might as well take the maximum running time:

n ↦ The maximum running time of a Turing machine (with no input) such that there exists a proof of halting in first order set theory (under the domain of the vN universe) using fewer than n symbols.

I think this is some weak version of the Rayo function now.

[Macbi]

I believe the fastest growing known computable functions are of the following form:

n ↦ The combined running time of all Turing machines (with no input) such that there exists a proof that they halt in second-order PA using fewer than n symbols

FIrst order set theory is much stronger, and you might as well take the maximum running time:

n ↦ The maximum running time of a Turing machine (with no input) such that there exists a proof of halting in first order set theory (under the domain of the vN universe) using fewer than n symbols.

I think this is some weak version of the Rayo function now.

Right. But the problem with your function is that you can't prove that it's total using ZF(C), which is the conventional axiom set for doing mathematics. I chose second order PA because it was the strongest axiom set I could think of that ZF can prove sound. Otherwise we could grow even faster by using ZF + large cardinal axiom.

[testitemqlstudop]

Wait, ZFC can't prove itself?