Largest total computable function competition

[fluffykitty]

Oh yeah nvm then

[testitemqlstudop]

I saw this order-(VERY LARGE) total uncomputable function on AoPS some time ago. (Modified to be a function)

Define a turing machine level X recursively as follows:

A level 0 turing machine is a standard turing machine with N states.
A level X != 0 turing machine is a turing machine with N states that has an oracle to the halting problem on a level X-1 turing machine.

F(0) = BB(10^100).
F(x) = Busy Beaver function on a level F(x-1) turing machine with F(x-1) states.

[fluffykitty]

That's probably less than f_(w_w^CK+1)(x)

[testitemqlstudop]

It's actually already described on the Googology Wiki, and it is in fact f_(w_w^CK+1)(x)

[testitemqlstudop]

Here's a new approach. I hope all of you know Python. Sadly uncomputable, but hopefully surpasses the Xi function.

Call this oracle.py:

Code: Select all

def oracle(code):
    if (code halts):
        return 0
    elif (code doesn't halt):
        return 1
    else:
        return -1

It is used in a similar way as exec - i.e. a block of code is passed to it as a Python string and it returns -1, 0, or 1.

My function py(x) = the maximum output made by a halting Python program under x characters given infinite time, the standard libraries and oracle.py (i.e. "import oracle")

[gameoflifemaniac]

What is Xi function

[Moosey]

What is Xi function

Maybe try the wiki everybody is talking about?
https://googology.wikia.org/wiki/Xi_function
In case you're curious what SKI calculus is:
https://en.m.wikipedia.org/wiki/SKI_combinator_calculus

Here's a new approach. I hope all of you know Python. Sadly uncomputable, but hopefully surpasses the Xi function.

Call this oracle.py:

Code: Select all

def oracle(code):
    if (code halts):
        return 0
    elif (code doesn't halt):
        return 1
    else:
        return -1

It is used in a similar way as exec - i.e. a block of code is passed to it as a Python string and it returns -1, 0, or 1.

My function py(x) = the maximum output made by a halting Python program under x characters given infinite time, the standard libraries and oracle.py (i.e. "import oracle")

How exactly would you have oracle return -1? And isn't that function undefined for large x? If you made it a quine-thing so that its output (I.e. all the code) is fed into the oracle, I'm sure there's a clever way to set it up so that you have some real nice shenanigans. Berry's paradox may be possible, etc. Ergo: py(x) is probably undefined for large enough x.
Something like looking at the length of the code, trying all length+1-long combinations that halt (since it can test whether code halts), and then outputting that output, +1. There's just one issue: this must by definition halt since the meat of its code halts and then it does a real simple addition to the result, but obviously its code plus a space or whatever is going to be largest. And that will be the same as its code plus a space-- this means that for large enough x py(x) will be the largest value attainable by a python program of any length-- ergo, it's undefined.

[gameoflifemaniac]

What is Xi function

Maybe try the wiki everybody is talking about?
https://googology.wikia.org/wiki/Xi_function
In case you're curious what SKI calculus is:
https://en.m.wikipedia.org/wiki/SKI_combinator_calculus

Here's a new approach. I hope all of you know Python. Sadly uncomputable, but hopefully surpasses the Xi function.

Call this oracle.py:

Code: Select all

def oracle(code):
    if (code halts):
        return 0
    elif (code doesn't halt):
        return 1
    else:
        return -1

It is used in a similar way as exec - i.e. a block of code is passed to it as a Python string and it returns -1, 0, or 1.

My function py(x) = the maximum output made by a halting Python program under x characters given infinite time, the standard libraries and oracle.py (i.e. "import oracle")

How exactly would you have oracle return -1? And isn't that function undefined for large x? If you made it a quine-thing so that its output (I.e. all the code) is fed into the oracle, I'm sure there's a clever way to set it up so that you have some real nice shenanigans. Berry's paradox may be possible, etc. Ergo: py(x) is probably undefined for large enough x.

my brain is too small

[Moosey]

What is Xi function

Maybe try the wiki everybody is talking about?
https://googology.wikia.org/wiki/Xi_function
In case you're curious what SKI calculus is:
https://en.m.wikipedia.org/wiki/SKI_combinator_calculus

Here's a new approach. I hope all of you know Python. Sadly uncomputable, but hopefully surpasses the Xi function.

Call this oracle.py:

Code: Select all

def oracle(code):
    if (code halts):
        return 0
    elif (code doesn't halt):
        return 1
    else:
        return -1

It is used in a similar way as exec - i.e. a block of code is passed to it as a Python string and it returns -1, 0, or 1.

My function py(x) = the maximum output made by a halting Python program under x characters given infinite time, the standard libraries and oracle.py (i.e. "import oracle")

How exactly would you have oracle return -1? And isn't that function undefined for large x? If you made it a quine-thing so that its output (I.e. all the code) is fed into the oracle, I'm sure there's a clever way to set it up so that you have some real nice shenanigans. Berry's paradox may be possible, etc. Ergo: py(x) is probably undefined for large enough x.

my brain is too small

I updated that post too:

[a Berry's paradox (pseudo)code]
Something like looking at the length of the code, trying all length+1-long combinations that halt (since it can test whether code halts), and then outputting that output, +1. There's just one issue: this must by definition halt since the meat of its code halts and then it does a real simple addition to the result, but obviously its code plus a space or whatever is going to be largest. And that will be the same as its code plus a space-- this means that for large enough x py(x) will be the largest value attainable by a python program of any length-- ergo, it's undefined.

[Moosey]

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.

[testitemqlstudop]

ergo, it's undefined.

Duh, that's why oracle.py can return -1 for a piece of code.

[Moosey]

ergo, it's undefined.

Duh, that's why oracle.py can return -1 for a piece of code.

That's not what I mean--py(x) = undefined for large enough x because ∃(code|code halts)∀(programs|programs halt && programs longer than code)(code output > programs output). You can construct code that halts, yet runs all 1 longer halting codes and adds one to their outputs. It will attain an arbitrarily large output value, by running itself + a space, yet it must halt.

[testitemqlstudop]

I'd like to see how you can achieve embedding py(x) x+1 character codes in a program of length x - zip compression?

[fluffykitty]

Code: Select all

from sys import argv
from oracle import oracle
oracle("".join(open(argv[0])))

is a paradox (to test, remove line 2 and replace oracle with print)

[Moosey]

I'd like to see how you can achieve embedding py(x) x+1 character codes in a program of length x - zip compression?

Easy. I covered that in the original post; it just runs a loop which runs through every length+1-character program by generating every possible length+1 string and then using oracle.py only running those that halt and then adding one to the largest output. It will run codes like

Code: Select all

asdfghjkl

Which of course isn't code so it would just ignore those.
But it will inevitably run over its own code, plus a space...

[PkmnQ]

ownKnanakshsj{)

Translation: Wrong thread

[Moosey]

ownKnanakshsj{)

Translation: Wrong thread

We know the py stuff is uncomputable but we can discuss uncomputable stuff here--we just try not to.
EDIT: and related, mooseudocode + oracle.hnfmf (hypothetical name for mooseudocode file) + runMooseudocodeString.hnfmf is definitely undefined:

Code: Select all

#this is a comment!
call oracle #call is like import in python
call runMoosedocodeString as run
call numbertostring #(a hypothetical code which could be written out
#but I don't want to right now since 1) I don't
#have it and 2) it would be long.
#basically, it just converts a number to a string. e.g. 1-> a, 2 -> b,
#(something around 30 or 40) -> aa, etc.
newvar x
newvar i
newvar y
newset A
x=0
i=0
protect i #new syntax! protect -> don't change value during runMoosedocodeString.
protect A
deprotect x #(makes sure x will never be protected)
while i < 500^(this.length) #500 can be any value as long as it's greater than the
#number of characters mooseudocode uses.
->y = numbertostring(i) #we assign y to that string...
->if oracle(y) = 1,
-> ->newent A
-> ->setent i of A x #this shot in the dark is okay since we're going over every string.
#Even if some fast-growing thing assigning stuff to a z
#appears we'll still get one assigning stuff to x.
-> ->x=0
x=0
i=0
while i <= A.length
->if ent i of A > x
-> ->x=ent i of A

Returns an x equal to the largest output of a 1-longer string, as I described in the py(x) thing. If python has codes that interpret mooseudocode then py(x) is undefined for large enough x

[Moosey]

New extension to/relative of tilde-caret notation (found in the lower part of this post) I made during world history:

I claimed this was f_w^w(n), is it?

C804B11F-C6D7-4AC8-AE3F-43B1158B824E.jpeg (175.53 KiB) Viewed 7981 times

Is it f_w^4 or f_w^3 ish or is it f_w^w?
For those who are too lazy to look at the image: (also slightly modified to remove errors)

Code: Select all

Earlier rules take precedence
a{^b~_c^d}e = a^(^.e)a, b=c=d=1 (by a^(^.e)a I mean a and another a with e arrows between. And I don't mean 2.71828...)
a{^b~_c^d}e = 2+ (a{^b~_c^(d-1)}(a{^b~_c^d}e-1)), b>1, c>1, d>1, e>1  (the 2+ is solely to keep it enormous even if the latter value wouldn't otherwise evaluate to much)
a{^b~_c^d}e = a{^b~_c^(d-1)}(a{^b~_c^(d-1)}a), e=1
a{^b~_c^d}e = a{^(b-1)~_c^(a{^(b-1)~_c^d}a)}a, d = e = 1
a{^b~_c^d}e = a{^(a{^a~_(c-1)^a}a)~_(c-1)^a}a, b = d = e = 1

I wondered whether it was f_w^w since I tried specifically not to land lower (but no, I don't expect to reach e_0)
@Fluffykitty can you update that list?

[fluffykitty]

Looks like it's less than w^w. Rule of thumb: If you have more than three or four arguments, try to use all but one or two in a consistent way so they can share rules.

[testitemqlstudop]

Introducing the newest fad: passing functions to functions!

This is finite when F is finite, since x never increases, and will eventually hit F(y).

Code: Select all

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

Define F(n) = çσM(n+2).

example: œ(F, 100, 100)

If my intuition is right with good enough F it's very high in the fgh.

And is the SGH actually faster than the FGH?

[Moosey]

Introducing the newest fad: passing functions to functions!

This is finite when F is finite, since x never increases, and will eventually hit F(y).

Code: Select all

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

Define F(n) = çσM(n+2).

example: œ(F, 100, 100)

If my intuition is right with good enough F it's very high in the fgh.

If I did this right, which I doubt, but I tried my best to do so, then you could extend it beyond the çσM(n) sequence of çσM(n), gçσM(n)...
Otherwise, you could use a sufficiently generalized version of çσM(n).
Also, œ(a,b,c) reminds me of the content of the quote in this post. I believe œ has an error though: here it has only two arguments:
F(œ(x-1, F(x))) when y = 0
Perhaps you meant
F(œ(F, x-1, F(x))) when y = 0

And is the SGH actually faster than the FGH?

Only for large enough ordinals, according to Wikipedia, the incredibly unreliable resource™.

[fluffykitty]

The SGH can match the FGH's strength, but it will never exceed it.

[testitemqlstudop]

On Googology WIkia it says the SGH will surpass the FGH for "large enough ordinals" and "depending on the definition".

Whoops, yes, œ is supposed to have three arguements...

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
}

EDIT:

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.

[PkmnQ]

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
}

Remind me again, how does F^x(n) work? I wanna experiment what happens if I put in different functions.

[testitemqlstudop]

F^x(y) = F(F(F(... x times ... F(F(y)) ... x times ... )))