Largest total uncomputable function competition

[testitemqlstudop]

Too uncomputable:

f(x) = fastest growing function on the fgh using standard fundamental sequence under first omega fixed point, definable in under x bytes, with no expanding references to other functions

like if it tries to refer to itself it would technically have infinte size, disqualifying it

I used fseq before fofp because even tho you can't actually define it, my function arguably has growth rate w_1 since it dominates all functions indexable by countable ordinals

[Moosey]

It's not inconceivable that doing this sort of thing in English is just impossible, i.e. all ways to try this with English are ultimately illdefined. I'm sure there's a loophole in your berry paradox loophole, unfortunately.

[toroidalet]

I'm fairly confident you can't define a fundamental sequence for ω_1^CK in a finite number of bits, since otherwise you could use the representation to compute the sequence and thus the Busy Beaver function.

Also, getting a function with growth rate ω_1 is problematic, since ω_1 has no fundamental sequences of length ω (or any countable ordinal), and so the FGH cannot be defined for it. (I wonder whether anyone's proven that any arithmetic function is dominated by an FGH function with some countable ordinal)

[testitemqlstudop]

Fine, how about instead of FGH, we use something called "function domination hierarchy", where functions are mapped to real numbers in the following rule:

f = integer map to another integer

FDF(f1) > FDF(f2) if and only if f1 >* f2

Such a mapping provably exists, since the cardinality of the real numbers = cardinality of countable ordinals.
You don't even need a fundamental sequence here.

[Moosey]

Also, getting a function with growth rate ω_1 is problematic, since ω_1 has no fundamental sequences of length ω (or any countable ordinal), and so the FGH cannot be defined for it. (I wonder whether anyone's proven that any arithmetic function is dominated by an FGH function with some countable ordinal)

What if we used a fgh modification that took [a] of the index b where cardinality(a)<cardinality(b) and a is not always finite?

[PkmnQ]

W(x) = 1/(the chance of making an x-letter word in english by just picking random letters)

For example
W(1) = 1/(2/26) = 13
W(2) = 1/(107/676) = 6.31ish
W(3) = 1/(1015/17576) = 17.31ish

It’s definitely always less than 26^x. That’s easy to say.

[PkmnQ]

Also, getting a function with growth rate ω_1 is problematic, since ω_1 has no fundamental sequences of length ω (or any countable ordinal), and so the FGH cannot be defined for it. (I wonder whether anyone's proven that any arithmetic function is dominated by an FGH function with some countable ordinal)

Isn’t the fundamental sequence

Code: Select all

w, w^w, w^w^w, w^w^w^w

[Moosey]

Also, getting a function with growth rate ω_1 is problematic, since ω_1 has no fundamental sequences of length ω (or any countable ordinal), and so the FGH cannot be defined for it. (I wonder whether anyone's proven that any arithmetic function is dominated by an FGH function with some countable ordinal)

Isn’t the fundamental sequence

Code: Select all

w, w^w, w^w^w, w^w^w^w

No.
That's the pathetically tiny (by comparison) e_0

[testitemqlstudop]

let's revive this thread

Consider the standard Brainfuck program, but equip it with W_1 more commands, one for each countable ordinal.

Call the order of the current state as the maximum previously encountered ordinal. The final order of any Brainfuck program (halting or non-halting) is the supremum of all ordinals encountered through execution. This is defined for non-halting Brainfuck programs, as we only define the limit superior.

If the order of the current state is A, then the program has the ability to solve the Turing halting problem for all Brainfuck programs with final order strictly less than A. The program will be equipped with another "oracle" state, in which the current tape state is represented as another Brainfuck program, and the current pointer value becomes 0 or 1, depending on whether or not the previous Brainfuck program halts or not.

The power of such a program is equal to w_{w_1}^CK, if such is even defined.

Formality:

The starting order is always 0.
Note that if the current order is w, then it cannot solve the halting problem for order w, only for integers, since w !< w

[toroidalet]

Assuming your function is defined, its strength would still be less than ω_1 (we can remove the CK because all admissible ordinals of countable order are countable) because you can view it as the diagonalization across f_ω_α(n)^CK, where α(n) is the minimum order of the busy beaver equivalent for n (among all possible winners, one (or multiple) of them must have the lowest order). As the limit of any countable series of ordinals is countable, your function must have a countable strength (probably some CK fixed point or something).

Also, how are you going to compress uncountably many ordinals into the countably many configurations of a tape?

[testitemqlstudop]

Let's say the tape manipulates reals instead of integers.