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.testitemqlstudop wrote:I don't think that's total computable, at also, that's known as Busy Beaver.
Largest total computable function competition
Re: Largest total computable function competition
-
- Posts: 1175
- Joined: June 14th, 2014, 5:03 pm
- Contact:
Re: Largest total computable function competition
I think you need to be significantly more precise with your definitions to produce a concrete function.
-
- Posts: 795
- Joined: May 30th, 2016, 8:47 pm
- Location: Milky Way Galaxy: Planet Earth
Re: Largest total computable function competition
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!
Re: Largest total computable function competition
That’s cheatingGamedziner 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.
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
Code: Select all
TREEfancy(n,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
Re: Largest total computable function competition
What is he growth rate of
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.
If instead of varying the second argument, you vary the first? Or both!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.
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
- testitemqlstudop
- Posts: 1367
- Joined: July 21st, 2016, 11:45 am
- Location: in catagolue
- Contact:
Re: Largest total computable function competition
Not total computableGamedziner 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.
DID ANYONE SEE MY IMAGES
-
- Posts: 1175
- Joined: June 14th, 2014, 5:03 pm
- Contact:
Re: Largest total computable function competition
Correct. It is 1 FGH level above TREE.Moosey wrote: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.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.
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)Moosey wrote:What is he growth rate ofIf instead of varying the second argument, you vary the first? Or both!fluffykitty wrote:definition of my f(a,b)
i.e.
Define h(x,y) = f(2^x,y)
Nopetestitemqlstudop wrote:Not total computableGamedziner 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.
Both of those are probably below f_w.testitemqlstudop wrote:DID ANYONE SEE MY IMAGES
- testitemqlstudop
- Posts: 1367
- Joined: July 21st, 2016, 11:45 am
- Location: in catagolue
- Contact:
Re: Largest total computable function competition
The second one isn't.
Re: Largest total computable function competition
I truly wouldn’t know myself, but when it comes to fast-growing functions, I have a helpful rule of thumb:testitemqlstudop wrote:The second one isn't.
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
- testitemqlstudop
- Posts: 1367
- Joined: July 21st, 2016, 11:45 am
- Location: in catagolue
- Contact:
Re: Largest total computable function competition
Is ^ up-arrow or exponentiation?
Re: Largest total computable function competition
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.testitemqlstudop wrote:Is ^ up-arrow or exponentiation?
not active here but active on discord
- testitemqlstudop
- Posts: 1367
- Joined: July 21st, 2016, 11:45 am
- Location: in catagolue
- Contact:
Re: Largest total computable function competition
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.
Re: Largest total computable function competition
Define §_m,n(x,y,z)=
How fast does it grow?
And where is ggç in the FGH?
Remember, ggç_p,m,n(x,y,z)=
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.
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
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
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
Re: Largest total computable function competition
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.
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.
Re: Largest total computable function competition
Is that all?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.
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
Re: Largest total computable function competition
I cut out all the unnecessary information.Moosey wrote: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).PkmnQ wrote:I’m submitting this, even without factorials, because these are getting ridiculous.
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.
-
- Posts: 1175
- Joined: June 14th, 2014, 5:03 pm
- Contact:
Re: Largest total computable function competition
Actually, S∈P(S) so all of the functions in that post are infinite.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.
I'll probably respond to everything else here in the evening.
EDIT:
It doesn't since the last case ignores everything except m, which never changes.Moosey wrote:Define §_m,n(x,y,z)=How fast does it grow?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
[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
It is most likely w^3. Reaching w^w requires infinite arguments unless you use more sophisticated methods.
This function is below f_w.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)
Re: Largest total computable function competition
[quote="Test]Hi[/quote]
Test wrote:Hello
- testitemqlstudop
- Posts: 1367
- Joined: July 21st, 2016, 11:45 am
- Location: in catagolue
- Contact:
Re: Largest total computable function competition
No, there are only 26 layers, so it is finite. It does not recurse infinitely.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.
OH the infinite recursion
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
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
- testitemqlstudop
- Posts: 1367
- Joined: July 21st, 2016, 11:45 am
- Location: in catagolue
- Contact:
Re: Largest total computable function competition
Bamp
My function
My function
Re: Largest total computable function competition
Yes...?testitemqlstudop wrote:Bamp
My function
not active here but active on discord
- gameoflifemaniac
- Posts: 1242
- Joined: January 22nd, 2017, 11:17 am
- Location: There too
Re: Largest total computable function competition
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!
Re: Largest total computable function competition
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?
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
-
- Posts: 1175
- Joined: June 14th, 2014, 5:03 pm
- Contact:
Re: Largest total computable function competition
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.
Re: Largest total computable function competition
Which thread? I probably read it, but...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.
not active here but active on discord