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
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Largest total computable function competition

Post by Macbi » June 7th, 2019, 10:17 am

testitemqlstudop wrote:I don't think that's total computable, at also, that's known as Busy Beaver.
The Busy Beaver function looks at all Turing machines of a given size that halt, whereas I'm only looking at the subset of those that can be proven to halt in second-order PA (with a proof of length ≤n). This is computable since one can just look at each string of length ≤n and see if it's a proof in second-order PA that a Turing machine halts.

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

Re: Largest total computable function competition

Post by fluffykitty » June 7th, 2019, 3:14 pm

I think you need to be significantly more precise with your definitions to produce a concrete function.

Gamedziner
Posts: 795
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Re: Largest total computable function competition

Post by Gamedziner » June 7th, 2019, 3:17 pm

TREE(TREE(TREE(…n))),where "n" is also the number of instances of "TREE(," is MUCH larger than TREE(n) for all positive integers n that are greater than or equal to 2.

Code: Select all

x = 81, y = 96, rule = LifeHistory
58.2A$58.2A3$59.2A17.2A$59.2A17.2A3$79.2A$79.2A2$57.A$56.A$56.3A4$27.
A$27.A.A$27.2A21$3.2A$3.2A2.2A$7.2A18$7.2A$7.2A2.2A$11.2A11$2A$2A2.2A
$4.2A18$4.2A$4.2A2.2A$8.2A!

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Largest total computable function competition

Post by Moosey » June 7th, 2019, 3:28 pm

Gamedziner wrote:TREE(TREE(TREE(…n))),where "n" is also the number of instances of "TREE(," is MUCH larger than TREE(n) for all positive integers n that are greater than or equal to 2.
That’s cheating

I might as well just say:
f(n)=
1+ the current largest known computable function besides this function (this function is not considered in any other function like this)

And no matter how hard you tried, you wouldn’t be able to beat this without copying it and saying 1+ it.

Also, I don’t think that’s much higher in the hierarchy than TREE(n), as, according to my extremely limited understanding of what fluffykitty said, that’s only ω or possibly 1 farther.



Anyways, if you’re gonna make that function, I’ll make a function based on it

TREEfancy(m,n)=

Code: Select all

TREE(TREEfancy(m,n-1)), n>0
m, n=0
gmdznrTREE(n) (your function)=

Code: Select all

TREEfancy(n,n)
msygdznrTREE(m,n)=

Code: Select all

this is, by the way, intended to be somewhat salad-y
gmdznrTREE(mn)msygdznrTREE(m-1,n), m>n, n>0
msygdznrTREE((m+1)^gmdznrTREE(m+1),n-1), m=n, n>0
3, n=0
Last edited by Moosey on September 11th, 2019, 5:56 pm, edited 1 time in total.
not active here but active on discord

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Largest total computable function competition

Post by Moosey » June 7th, 2019, 6:05 pm

What is he growth rate of
fluffykitty wrote:Here's a somewhat boring entry:
f(0,x)=x
f(a,x)=f(g(a,a,x),x+1)
g(4b+2,x,n)=b
g(a,x,0)=0
g(4b+1,x,n+1)=2^g(x,x,n)*(4b+2)
g(2^a*(4b+2),x,n+1)=2^g(a,a,n+1)*(4*g(2^a*(4b+2),x,n)+2)
g(2^a*(4b+2)-1,x,n+1)=2^g(a,x,n+1)*(4*g(2^a*(4b+2)-1,x,n)+2)-1
Submit f(2^2^16,n)
If you want to test this function, use something like f(8,n) since even f(2^2^16,1) is massive.
Approximations of other functions:
Successor: f(2,n)
Weak Goodstein sequences/Ackermann function: f(512,n)
Strong Goodstein sequences/Simple hydras/tree: f(4,n)
TREE: f(2^(2^2046-1),n)
Something stronger than TREE: f(2^2^16,n)
Odd first arguments of f are not guaranteed to work correctly.
If instead of varying the second argument, you vary the first? Or both!
i.e.
Define h(x,y) = f(2^x,y)

h(0,0)= f(1,0) = f(0,1)=1
h(0,1)= f(1,1) = f(g(1,1,1),2) = f(2^(2g(1,1,0),2)= f(1,2)...
Does somebody have a python program for this or something?

EDIT:
I meant to post this elsewhere but I think this thread is fine.
not active here but active on discord

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 » June 7th, 2019, 8:28 pm

Gamedziner wrote:TREE(TREE(TREE(…n))),where "n" is also the number of instances of "TREE(," is MUCH larger than TREE(n) for all positive integers n that are greater than or equal to 2.
Not total computable

DID ANYONE SEE MY IMAGES

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

Re: Largest total computable function competition

Post by fluffykitty » June 7th, 2019, 11:08 pm

Moosey wrote:
Gamedziner wrote:TREE(TREE(TREE(…n))),where "n" is also the number of instances of "TREE(," is MUCH larger than TREE(n) for all positive integers n that are greater than or equal to 2.
Also, I don’t think that’s much higher in the hierarchy than TREE(n), as, according to my extremely limited understanding of what fluffykitty said, that’s only ω or possibly 1 farther.
Correct. It is 1 FGH level above TREE.
Moosey wrote:What is he growth rate of
fluffykitty wrote:definition of my f(a,b)
If instead of varying the second argument, you vary the first? Or both!
i.e.
Define h(x,y) = f(2^x,y)
f(2^^x,x) is comparable to f_(Bachmann-Howard ordinal) if I defined everything correctly. h(x,x) is slower, but not by very much (it's still faster than FGH f_x for any x less than the Bachmann-Howard ordinal)
testitemqlstudop wrote:
Gamedziner wrote:TREE(TREE(TREE(…n))),where "n" is also the number of instances of "TREE(," is MUCH larger than TREE(n) for all positive integers n that are greater than or equal to 2.
Not total computable
Nope
testitemqlstudop wrote:DID ANYONE SEE MY IMAGES
Both of those are probably below f_w.

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 » June 7th, 2019, 11:37 pm

The second one isn't.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Largest total computable function competition

Post by Moosey » June 8th, 2019, 7:07 am

testitemqlstudop wrote:The second one isn't.
I truly wouldn’t know myself, but when it comes to fast-growing functions, I have a helpful rule of thumb:
fluffykitty is rarely wrong, so I feel it is only ω-neighborhood.

It never hurts to remember that ω is pretty fast already, faster-growing than, say, BUNDLEPARTY(n) or even ltr_c(n,n,n) if you don’t vary c. f_ω(n) ~= n^ⁿn
Last edited by Moosey on June 8th, 2019, 7:10 am, edited 1 time in total.
not active here but active on discord

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 » June 8th, 2019, 7:10 am

Is ^ up-arrow or exponentiation?

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Largest total computable function competition

Post by Moosey » June 8th, 2019, 7:11 am

testitemqlstudop wrote:Is ^ up-arrow or exponentiation?
Generally many people who don’t want to go to the Unicode table use ^ as an up arrow—since a(uparrow)b = a^b it doesn’t interfere with anything, and you should be able to assume people can tell nⁿn from n^ⁿn. Of course you know this, so I’ll answer your question now: up-arrow.
not active here but active on discord

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 » June 8th, 2019, 7:30 am

True, the 1st is something along the lines of 2^^^^^^^^^^^^^^^^^^^^^^^^^n*n!^^^^^...^^^n!, but the 2nd is much, much larger. I think I actually disagree with fluffykitty on this; you can experiment with 4 functions instead of 26.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Largest total computable function competition

Post by Moosey » June 8th, 2019, 7:58 am

Define §_m,n(x,y,z)=

Code: Select all

§_m,n(x,y-1,z)§_m,n(§_m,n(x,y-1,z),y-1,z), y>0
§_m,n(x,§_m,n(x,x,z-1),z-1), y=0, z>0
§_m,n-1(x,§_m,n-1(x,x,x),§_m,n-1(§_m,n-1(x,x,x),x,x)), y=0, z=0, n>0
m, n=0
How fast does it grow?

And where is ggç in the FGH?
Remember, ggç_p,m,n(x,y,z)=

Code: Select all

ggç_p,m,n-1(x,x,x)ggç_p,m,n(ggç_p,m,n-1(x,x,x),y-1,z), n >0, y>0, m>0
ggç_p,m,n-1(x,x,x)ggç_p,m,n(ggç_p,m,n-1(x,x,x),x,z-1), n > 0, y = 0, z>0, m>0
ggç_p,m,n-1(x,x,x)ggç_p,m,(n-1)(ggç_p,m,n-1(x,x,x),x,x), n > 0, z = 0,y=0, m>0
ggç_p,m-1,x(x,x,x), n=0, m>0
ggç_p-1,x,x,(x,x,x), m = 0, p>0
f(x,x,x), p=0
I guess maybe it’s ω^ω, since gç is ω^2 neighborhood.
Okay I was wrong for future reference

I kinda want to start a competition to find a function which takes finite numbers and returns countable ordinals.
Last edited by Moosey on September 11th, 2019, 5:55 pm, edited 3 times in total.
not active here but active on discord

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

Re: Largest total computable function competition

Post by PkmnQ » June 8th, 2019, 9:49 am

I present to you, the ThisCount function. Based off my previous one, but no tricky factorials.
It is independent, only recursion, parentheses, and 4 basic operations. Well, 3, because division doesn’t help.

I’m submitting this, even without factorials, because these are getting ridiculous.
It’s like 34Life.
I’m hoping that this will end up being actual Life.

ThC(x,y,z) = (xy+x+y) * ThC(xz,y,z-1)
ThC(x,y,0) = (xy+x+y) * ThC(xy,y-1,xy)
ThC(x,0,0) = x

f(x) = ThC(x,x,x)

f(1) = 18
f(2) = 8 * 14 * 14 * 17 * 129 * 897 * 5377 * 26881 * 107521 * 322561 * 645123 * 645123 * 322561^322561

...Yeah.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Largest total computable function competition

Post by Moosey » June 8th, 2019, 10:23 am

PkmnQ wrote:I present to you, the ThisCount function. Based off my previous one, but no tricky factorials.
It is independent, only recursion, parentheses, and 4 basic operations. Well, 3, because division doesn’t help.

I’m submitting this, even without factorials, because these are getting ridiculous.
It’s like 34Life.
I’m hoping that this will end up being actual Life.
...
f(2) = 8 * 14 * 14 * 17 * 129 * 897 * 5377 * 26881 * 107521 * 322561 * 645123 * 645123 * 322561^322561

...Yeah.
Is that all?
8 * 14 * 14 * 17 * 129 * 897 * 5377 * 26881 * 107521 * 322561 * 645123 * 645123 * 322561^322561 << g_64 << a lot of other numbers posted in this thread, including the many I posted in this thread (σM(2), for instance).

I don’t think that the growth rate of f or ThC is comparable to, e.g. n^ⁿn— it grows quickly, but is probably outpaced by n^ⁿn at larger n.
not active here but active on discord

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

Re: Largest total computable function competition

Post by PkmnQ » June 8th, 2019, 11:06 am

Moosey wrote:
PkmnQ wrote:I’m submitting this, even without factorials, because these are getting ridiculous.
ThC(2,2,2) << g_64 << a lot of other numbers posted in this thread, including the many I posted in this thread (σM(2), for instance).
I cut out all the unnecessary information.

Also, fluffykitty’s function.
I will now proceed to call it y(a,x)
And y(1,x) just so happens to be the Mersenne Sequence.

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

Re: Largest total computable function competition

Post by fluffykitty » June 8th, 2019, 3:28 pm

testitemqlstudop wrote:True, the 1st is something along the lines of 2^^^^^^^^^^^^^^^^^^^^^^^^^n*n!^^^^^...^^^n!, but the 2nd is much, much larger. I think I actually disagree with fluffykitty on this; you can experiment with 4 functions instead of 26.
Actually, S∈P(S) so all of the functions in that post are infinite.
I'll probably respond to everything else here in the evening.
EDIT:
Moosey wrote:Define §_m,n(x,y,z)=

Code: Select all

§_m,n(x,y-1,z)§_m,n(§_m,n(x,y-1,z),y-1,z), y>0
§_m,n(x,§_m,n(x,x,z-1),z-1), y=0, z>0
§_m,n-1(x,§_m,n-1(x,x,x),§_m,n-1(§_m,n-1(x,x,x),x,x)), y=0, z=0, n>0
m, n=0
How fast does it grow?
It doesn't since the last case ignores everything except m, which never changes.
[quote="Moosey]
And where is ggç in the FGH?
Remember, ggç_p,m,n(x,y,z)=

Code: Select all

ggç_p,m,n-1(x,x,x)ggç_p,m,n(ggç_p,m,n-1(x,x,x),y-1,z), n >0, y>0, m>0
ggç_p,m,n-1(x,x,x)ggç_p,m,n(ggç_p,m,n-1(x,x,x),x,z-1), n > 0, y = 0, z>0, m>0
ggç_p,m,n-1(x,x,x)ggç_p,m,(n-1)(ggç_p,m,n-1(x,x,x),x,x), n > 0, z = 0,y=0, m>0
ggç_p,m-1,x(x,x,x), n=0, m>0
ggç_p-1,x,x,(x,x,x), m = 0, p>0
f(x,x,x), p=0
I guess maybe it’s ω^ω, since gç is ω^2 neighborhood.[/quote]
It is most likely w^3. Reaching w^w requires infinite arguments unless you use more sophisticated methods.
PkmnQ wrote:I present to you, the ThisCount function. Based off my previous one, but no tricky factorials.
It is independent, only recursion, parentheses, and 4 basic operations. Well, 3, because division doesn’t help.

I’m submitting this, even without factorials, because these are getting ridiculous.
It’s like 34Life.
I’m hoping that this will end up being actual Life.

ThC(x,y,z) = (xy+x+y) * ThC(xz,y,z-1)
ThC(x,y,0) = (xy+x+y) * ThC(xy,y-1,xy)
ThC(x,0,0) = x

f(x) = ThC(x,x,x)
This function is below f_w.

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

Re: Largest total computable function competition

Post by PkmnQ » June 8th, 2019, 9:34 pm

[quote="Test]Hi[/quote]
Test wrote:Hello

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 » June 8th, 2019, 9:39 pm

fluffykitty wrote: Actually, S∈P(S) so all of the functions in that post are infinite.
I'll probably respond to everything else here in the evening.
No, there are only 26 layers, so it is finite. It does not recurse infinitely.
OH the infinite recursion :oops:

How about this:

(1st version)
S is set, l is integer
F(S, l not 0) = |S|!prod^(U∈P(S)\{S})F((S),l)F(P(S),l-1)
F(S, 0) = |S|!prod^(U∈P(S)\{S})F(S,l)

(2nd version)
S is set, l is integer
fP = fancy pee
Define fP(S, l) as

Code: Select all

S, l=0
P(fP(S,l-1)) l != 0
Define F(S, l) as

Code: Select all

|S|!prod^(U∈P(S)\{S})prod^l_{k=0}F(fP(S, k),l-k)        where l != 0
2 where l = 0
[/code]

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 » June 11th, 2019, 9:45 am

Bamp

My function

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Largest total computable function competition

Post by Moosey » June 11th, 2019, 10:07 am

testitemqlstudop wrote:Bamp

My function
Yes...?
not active here but active on discord

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Largest total computable function competition

Post by gameoflifemaniac » June 11th, 2019, 1:00 pm

damn, this is beyond science
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Largest total computable function competition

Post by Moosey » June 11th, 2019, 1:12 pm

If anyone needs to represent fgh levels with finite numbers, try ord(n) (the function at top is used in the definition of ord(n) but is not ord(n)). It doesn’t exactly have a definition yet, but I think the definition would be pretty obvious for some of you (I encourage you to do it, defining it only in terms of (a,b) and itself)

ord(n) doesn’t really have a place in here as fast-growing, because
1) It’s infinite at many values
2) It’s really jumpy— ord(2) = w, ord(3)=2, ord(4)= w^^2 = w^w

Loosely, ord(2^^w) is ε_0 but it doesn’t really make sense since 2^^w = w, and ord(w) would be impossible to find.
I think that ord(n) is probably capable of mapping the set of all integers to the set of all ordinals >= 0 and < ε_0, so it works for getting lower countable ordinals. Clever tricks (e.g. extending ord(n) to be defined for any countable ordinal as well as integers) are necessary to get to ε_0, no doubt, but once there it could plausibly return ordinals as up to at least as large as Γ_0.

Anyways, that’s my assistance to those who need arguments that are infinite but are hesitant to want a huge mess of ωs lying around in their function.



EDIT:
@fluffykitty, is it even possible to define a function somehow related to ggç which is >= ε_0?
It seems that, if so, I’ll need to step out of Peano arithmetic, though I guess ord(n) maybe does that.


It should be possible to make an egç (extremely generalized ç) which somehow uses an ordinal to output extremely large finite numbers, I suppose, but how would I do so?
not active here but active on discord

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

Re: Largest total computable function competition

Post by fluffykitty » June 11th, 2019, 2:44 pm

If you want to go past ε_0, you can make a notation that includes ε_x, or for more power, Veblen functions or ordinal collapsing functions (which my f uses). I already posted some information regarding a method of creating an egç in another thread.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Largest total computable function competition

Post by Moosey » June 11th, 2019, 3:07 pm

fluffykitty wrote:If you want to go past ε_0, you can make a notation that includes ε_x, or for more power, Veblen functions or ordinal collapsing functions (which my f uses). I already posted some information regarding a method of creating an egç in another thread.
Which thread? I probably read it, but...
not active here but active on discord

Post Reply