Largest total uncomputable function competition

[testitemqlstudop]

Because I evidently pissed of pkmnq on the other thread.

Uncomputable function hierarchy:

w_(-1)^CK achieved by PP(N), WW(N) not wwei n
w_1^CK achieved by BB(N), FF(N),
w_w^CK achieved by diagonal n-th order BB, FF and Rayo function
a = w_a^CK achieved by Xi function (claimed)

Unfortunately, there is effectively no supremum of the uncomputable functions in general but only for fixed-order uncomputable functions (BB, FF)

Is it (theoretically) possible to get w_(w_1^CK)^CK?

[toroidalet]

What happens to the power of the Xi function if we replace the O combinator with O(x)(y)(z)(w)=y iff x reduces to I z iff it doesn't, and w if x is not well-founded?

[testitemqlstudop]

That would effectively allow SKIO calculus to evaluate the Xi function itself, allowing for even faster growth.

Calcyman contemplated this in his original blog post.

[toroidalet]

I'm pretty sure it would be at least the diagonalisation of order-n xi functions as opposed to order 2, since it can perform the functions of all the order-n oracle combinators.

On a related note, what's the next step after well-foundedness? Something to do with the pathological self-referential trees?

[PkmnQ]

Because I evidently pissed of pkmnq on the other thread.

No.

Explanation:
I was thinking of some strange way to make a function.
I decided “ok, i’ll try something else”
And listed all 2-letter words. Guess what thread I was on?
*hits edit*
“DSL uh fuhh”
What am Idoing?
“Translation: Wrong Thread”
There, that should clarify what I did without any confusion whatsoever. I mean, it’s not li-
*this thread*

[Moosey]

I think this function is worth noting as pathetically weak but still uncomputable. Note that I specifically stated it to be defined as the smallest value not attainable in a length n code and not the largest one attainable. This obviously makes it defined since there is a finite amount of codes however it is probably upperbounded by even something like 64^n assuming only one output is allowed (since there is a limited amount of distinct codes, the largest it can get would be the amount of distinct codes).
A different function, mpc(n) = the largest attainable finite value in n characters of mooseudocode, would be much much much much much much much more powerful but would have obvious undefined value issues. And if I introduced an oracle, that would have issues like those with py(x). Eh, I'll start w/o oracles and call it mpc_0(n)
If you disallowed oracles except for those which work exclusively across oracle-less functions, then you could have a new function, mpc_1(n) which would of course also quickly become undefined but who cares.
Then you could have mpc_2(n) which would disallow oracles except those which work exclusively across valid codes for mpc_1(n)
Then, to generalize, mpc_(m+1)(n) would disallow oracles except those which work exclusively across valid codes for mpc_m(n), which would of course mean we could have fun with the uncomputable function in question.
Of course, it would become undefined rapidly but I'm fine with that.

[testitemqlstudop]

Calcyman's first Xi function is claimed to have growth E_0^CK, is that correct

What about the extended Xi function?

[Moosey]

Calcyman's first Xi function is claimed to have growth E_0^CK, is that correct

What about the extended Xi function?

I don't know, but rayo(n) grows faster so xi is slower than the 1st CK fixed point if rayo is as well.

[testitemqlstudop]

I heard rayo is only w^^2^CK

[testitemqlstudop]

I literally think this blows Rayo's function away.

Consider an axiom set A (FOST, Peano arithmetic, ZFC, etc). Define tt(A, n) as the supremum of all numbers uniquely identified by an expression in axiom set A in under n symbols. Rayo(n) is basically tt(FOST, n)+1.

Now, consider all axiom sets definable in under m symbols. Define TEST(m, n) as the supremum of tt(A, n) for all A uniquely definable in under m symbols.

It's trivial, now, to show that TEST(365005, 10^100) > Rayo(10^100).
(I chose 365005 for a very subtle reason)

[Moosey]

I literally think this blows Rayo's function away.

Consider an axiom set A (FOST, Peano arithmetic, ZFC, etc). Define tt(A, n) as the supremum of all numbers uniquely identified by an expression in axiom set A in under n symbols. Rayo(n) is basically tt(FOST, n)+1.

Now, consider all axiom sets definable in under m symbols. Define TEST(m, n) as the supremum of tt(A, n) for all A uniquely definable in under m symbols.

It's trivial, now, to show that TEST(365005, 10^100) > Rayo(10^100).
(I chose 365005 for a very subtle reason)

That is similar to oblivion and utter oblivion.
It is illdefined, since:
1. What do you mean by "definable in m symbols"?
You need a certain set of symbols, say, (), ,, ∃, ∀, ⇒, ⇔, OR, XOR, AND, =, !, ∈, {}
2. You can define axioms that make no sense and then use them to definite infinitely large numbers that the axioms assert are finite. Or you could Berry's paradox it with the same method:

Code: Select all

Axiom 1: L(A) = the largest number you can define in A symbols using these axioms.
Axiom 2: Berry's paradox is nonexistent and a lie. It is total crumbs.
+ ZFC/ZF/PA/FOST/FOOT/etc.

And please, before you do the "all axioms that don't permit Berry's paradox" thing and we have a pointless argument, baron münchausen will have something to say to you, namely that you're setting fairly arbitrary rules. (See axiomatic argument)

[testitemqlstudop]

Consider a Turing machine with another added state, "ascend", which makes a new tape called the "ascended tape" and all previous tapes are called "lower tapes". The head is allowed to read/write to the ascended tape and the lower tapes, and the ascended tape has the ability to solve the Halting problem for all lower tapes. Now, do BB on this turing machine.

Does this get to w_w^CK?

[testitemqlstudop]

Consider a Turing machine with another added state, "ascend", which makes a new tape called the "ascended tape" and all previous tapes are called "lower tapes". The head is allowed to read/write to the ascended tape and the lower tapes, and the ascended tape has the ability to solve the Halting problem for all lower tapes. Now, do BB on this turing machine.

Does this get to w_w^CK?

Now consider another state, "plane ascend", which makes a new ascension tape plane called the "ascended plane" and all previous planes are called "lower planes". The head is allowed to read/write to all tapes it had ever been on before, and the head's plane has the ability to solve the planar Halting problem for all lower planes.

Now consider another state, "realm ascend", which makes a new ascension tape plane realm called the "ascended realm" and all previous realms are called "lower realms". The head is allowed to read/write to all tapes it had ever been on before, and the head's realm has the ability to solve the realm-wise Halting problem for all lower realms.

Now consider another state, "flune ascend", which... you see where this is going.

Assuming my previous assumption is correct, this gets to (first omega fixed point)^CK.

Now, consider another state, "statewise extension", which extends the current rules of the tape head by the data in the current tape, plane, realm, flune, etc.

*Insert "is this an ITTM" meme*

[Moosey]

Consider a Turing machine with another added state, "ascend", which makes a new tape called the "ascended tape" and all previous tapes are called "lower tapes". The head is allowed to read/write to the ascended tape and the lower tapes, and the ascended tape has the ability to solve the Halting problem for all lower tapes. Now, do BB on this turing machine.

Does this get to w_w^CK?

It makes a TM that can solve its own halting problem, so I'd say you could do the mechanism we discussed on the googology wiki, but I'm not sure

[testitemqlstudop]

No it doesn't solve its own halting problem. It executes on a higher level as soon as it ascends; it can't descend. Hence, it can never solve its own halting problem, since to solve the halting problem on its current level it needs to ascend to the next level.

[toroidalet]

I'm pretty sure that "tape ascend" is ω_ω^CK (but much faster than the diagonal busy beaver), since it can access an arbitrary but finite (otherwise it would never halt) oracle level, making it the limit of all the oracle Turing machine functions. Similarly, "plane ascend" is ω_(ω^2)^CK,"space ascend" is ω_(ω^3)^CK, and "dimension ascend" is ω_(ω^ω)^CK.

The indices of the ordinals (as in the index of ω_ω^CK is ω) happen to correspond to the order structures of the tapes.



Personally, I'd prefer to formalise the "ascending" Turing machines as ones with a multi-dimensional tape, but that doesn't work too well for "dimension ascend".

[Moosey]

Would it be possible to define a large number as the smallest number larger than all numbers in some axiom set which believes some number is the largest?
e.g. you define a system which takes a number, describes a set of axioms with it, and then finds the largest number in the Said set of axioms.
I guess there could be some issues considering that you're working with a set of axioms that is obviously false.

[testitemqlstudop]

OMG I KNOW

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.

Define K as some extremely powerful system (ZFC + LCO?)

n |-> the maximum running time of a Python program with the oracle module, which has a proof in under n symbols of halting and another proof in under n symbols of well-definedness (using K)

Well duh this is infinite:

print("10000000000000000000000000000000000000000000000000000000.....

Alright,

n |-> the maximum running time of a Python program with the oracle module, under n bytes and unable to use external resources (open/argv/etc.) which has a proof in under n symbols of halting and another proof in under n symbols of well-definedness (using K)

[Moosey]

Ascending TMs

Consider a "Universe ascend" which can reach another Universe of dimensions.
Probably > w_(w^w)ck

You can extend this as far as you want... what would you need for w_e_0ck?

[testitemqlstudop]

Ascending TMs

Consider a "Universe ascend" which can reach another Universe of dimensions.

You can't. There isn't a next universe, we have already took up all the space...
...unless you index dimensions by ordinals, and invent some method of fixed-point leap. i.e. we originally had 1d, 2d, ... nd, but we leap to the next fixed point and get w-d, w+1-d, etc... after a enough set of leaps you can get to BHO or w_1^CK, allowing us w_(w_1^CK)^CK

[Moosey]

Ascending TMs

Consider a "Universe ascend" which can reach another Universe of dimensions.

You can't. There isn't a next universe, we have already took up all the space...

NO
You can totally escape all the dimentsions by going to the next thing past all spaces which eventually occupy the same finite dimension
You don't need to index the dimensions with ordinals, though that was more or less what I was proposing.

In that case, if you have the first TM who has its order-type in dimension indices, it would be the ordinal I like to call "a whack" (because a|->w_ack)

[toroidalet]

If for you, universes mean what I think they mean (each universe is a copy of the "dimension ascend" structure with the power to oracle any lower universe), then it would only be ω_(ω^(ω+1))^CK (in the future, I'll ignore the ω_^CK bit for convenience). Of course, you can add dimensions of universes to get ω^(ω^ω), add multiverses to get ω^((ω^ω)+1), and diagonalise along uni/multi/omni/whateververses to get ε_0 (EDIT: dimensions of universes is only ω^2ω, so ε_0 takes a lot more work). If you want to get to α=ω_α^CK, you basically have to construct a series of tapes with order type α, and it might just be easier to do something based on the method you used to generate the ordinal instead of ascending Turing machines.

If you mean something different by "universes", it might be much stronger.

By the way, has anyone figured out upper bounds on the higher-order Ξ functions?
EDIT2: Ξ_1 (1 halting oracle and 1 well-foundedness oracle) is definitely at least the second CK fixed point, and probably the first fixed point of CK fixed points.

[testitemqlstudop]

Let S_i be a set theory.
S_0 = ZFC, and S_i is the axiom set that can prove S_{i-1} well-founded.
Assume that S_i will always be provably well founded, since otherwise ZFC isn't a well founded set theory.
My function is the Rayo-analogue function. but instead of FOST we have S_{10^100}.
Has got to be larger than Utter Oblivion

[Moosey]

Let S_i be a set theory.
S_0 = ZFC, and S_i is the axiom set that can prove S_{i-1} well-founded.
Assume that S_i will always be provably well founded, since otherwise ZFC isn't a well founded set theory.
My function is the Rayo-analogue function. but instead of FOST we have S_{10^100}.
Has got to be larger than Utter Oblivion

Illdefined
There could be multiple different axiom sets S_i that can prove S_{i-1} welldefined.
Also since Utter Oblivion is illdefined since it's not formalized, "got to be larger than Utter Oblivion" does not make sense

[testitemqlstudop]

Let S_i be a set theory.
S_0 = ZFC, and S_i is the axiom set that can prove S_{i-1} well-founded.
Assume that S_i will always be provably well founded, since otherwise ZFC isn't a well founded set theory.
My function is the Rayo-analogue function. but instead of FOST we have S_{10^100}.
Has got to be larger than Utter Oblivion

Illdefined
There could be multiple different axiom sets S_i that can prove S_{i-1} welldefined.
Also since Utter Oblivion is illdefined since it's not formalized, "got to be larger than Utter Oblivion" does not make sense

Minimal S_i then, where "minimal" means "smallest Rayo-analogue value at 10^100"