Largest total computable function competition

A forum where anything goes. Introduce yourselves to other members of the forums, discuss how your name evolves when written out in the Game of Life, or just tell us how you found it. This is the forum for "non-academic" content.
User avatar
PkmnQ
Posts: 1085
Joined: September 24th, 2018, 6:35 am
Location: Server antipode

Re: Largest total computable function competition

Post by PkmnQ » September 8th, 2019, 3:44 am

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

Code: Select all

Function(‘a’+’lert(1)’)()
Mi povas parolas Esperanto. Ankaux, mi sxatas supon de fungoj.

User avatar
Moosey
Posts: 3764
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: Largest total computable function competition

Post by Moosey » September 8th, 2019, 6:13 am

testitemqlstudop wrote:
Moosey wrote: 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.
PkmnQ wrote:Oh, so if f(x) = 3x+2 then f^3(5) = 161?
Yes.
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Largest total computable function competition

Post by testitemqlstudop » September 9th, 2019, 1:01 am

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

User avatar
Moosey
Posts: 3764
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: Largest total computable function competition

Post by Moosey » September 9th, 2019, 6:52 am

testitemqlstudop wrote: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:
The googology wiki wrote:[salad numbers] are often coined by inexperienced googologists holding the false notions that a more complex definition is a more powerful one.
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

User avatar
PkmnQ
Posts: 1085
Joined: September 24th, 2018, 6:35 am
Location: Server antipode

Re: Largest total computable function competition

Post by PkmnQ » September 10th, 2019, 5:16 am

Moosey wrote:
testitemqlstudop wrote: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:
The googology wiki wrote:[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.
How to XSS:

Code: Select all

Function(‘a’+’lert(1)’)()
Mi povas parolas Esperanto. Ankaux, mi sxatas supon de fungoj.

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Largest total computable function competition

Post by testitemqlstudop » September 10th, 2019, 5:40 am

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.

User avatar
Moosey
Posts: 3764
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: Largest total computable function competition

Post by Moosey » September 10th, 2019, 6:47 am

testitemqlstudop wrote: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.
testitemqlstudop wrote:
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)
...
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

User avatar
PkmnQ
Posts: 1085
Joined: September 24th, 2018, 6:35 am
Location: Server antipode

Re: Largest total computable function competition

Post by PkmnQ » September 10th, 2019, 7:45 am

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)
How to XSS:

Code: Select all

Function(‘a’+’lert(1)’)()
Mi povas parolas Esperanto. Ankaux, mi sxatas supon de fungoj.

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Largest total computable function competition

Post by testitemqlstudop » September 10th, 2019, 7:59 am

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

EDIT: Whoops i meant oe

User avatar
PkmnQ
Posts: 1085
Joined: September 24th, 2018, 6:35 am
Location: Server antipode

Re: Largest total computable function competition

Post by PkmnQ » September 10th, 2019, 9:36 am

testitemqlstudop wrote: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?
How to XSS:

Code: Select all

Function(‘a’+’lert(1)’)()
Mi povas parolas Esperanto. Ankaux, mi sxatas supon de fungoj.

User avatar
Moosey
Posts: 3764
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: Largest total computable function competition

Post by Moosey » September 10th, 2019, 6:44 pm

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
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Largest total computable function competition

Post by testitemqlstudop » September 12th, 2019, 12:08 am

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.

User avatar
Moosey
Posts: 3764
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: Largest total computable function competition

Post by Moosey » September 13th, 2019, 4:54 pm

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:
PkmnQ wrote:
testitemqlstudop wrote: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:
A while ago, I wrote:
A while before that, I wrote: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?
Last edited by Moosey on October 3rd, 2019, 4:44 pm, edited 3 times in total.
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

User avatar
Moosey
Posts: 3764
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: Largest total computable function competition

Post by Moosey » September 24th, 2019, 5:16 pm

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 :roll:
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
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

User avatar
PkmnQ
Posts: 1085
Joined: September 24th, 2018, 6:35 am
Location: Server antipode

Re: Largest total computable function competition

Post by PkmnQ » September 25th, 2019, 6:22 am

I haven’t seen n[x] before.
How to XSS:

Code: Select all

Function(‘a’+’lert(1)’)()
Mi povas parolas Esperanto. Ankaux, mi sxatas supon de fungoj.

User avatar
Moosey
Posts: 3764
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: Largest total computable function competition

Post by Moosey » September 25th, 2019, 6:33 am

PkmnQ wrote: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
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Largest total computable function competition

Post by testitemqlstudop » September 25th, 2019, 8:25 pm

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

User avatar
Moosey
Posts: 3764
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: Largest total computable function competition

Post by Moosey » September 26th, 2019, 6:38 am

testitemqlstudop wrote: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
testitemqlstudop wrote:Your explanation is better than the one on goowiki
Thanks
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

User avatar
Moosey
Posts: 3764
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: Largest total computable function competition

Post by Moosey » October 3rd, 2019, 4:50 pm

(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 (:a: :b: :m: :v: (:o:) (:x:))
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

User avatar
Moosey
Posts: 3764
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: Largest total computable function competition

Post by Moosey » October 4th, 2019, 4:29 pm

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,#}
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Largest total computable function competition

Post by testitemqlstudop » October 4th, 2019, 9:30 pm

Yes, that's right for unidimensional arrays.

But I don't get anything above 2d

User avatar
BlinkerSpawn
Posts: 1977
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: Largest total computable function competition

Post by BlinkerSpawn » October 4th, 2019, 10:39 pm

testitemqlstudop wrote:
October 4th, 2019, 9:30 pm
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
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

Image

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Largest total computable function competition

Post by testitemqlstudop » October 4th, 2019, 11:11 pm

Macbi wrote:
June 7th, 2019, 9:29 am
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.

User avatar
Macbi
Posts: 766
Joined: March 29th, 2009, 4:58 am

Re: Largest total computable function competition

Post by Macbi » October 5th, 2019, 6:38 am

testitemqlstudop wrote:
October 4th, 2019, 11:11 pm
Macbi wrote:
June 7th, 2019, 9:29 am
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.

User avatar
testitemqlstudop
Posts: 1367
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Largest total computable function competition

Post by testitemqlstudop » October 5th, 2019, 7:50 am

Wait, ZFC can't prove itself?

Post Reply