Page 2 of 2
Re: Largest total uncomputable function competition
Posted: November 20th, 2019, 8:15 am
by 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
Re: Largest total uncomputable function competition
Posted: November 20th, 2019, 9:33 am
by 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.
Re: Largest total uncomputable function competition
Posted: November 20th, 2019, 9:43 pm
by 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)
Re: Largest total uncomputable function competition
Posted: November 21st, 2019, 12:39 am
by 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.
Re: Largest total uncomputable function competition
Posted: November 21st, 2019, 7:43 am
by Moosey
toroidalet wrote: November 20th, 2019, 9:43 pm
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?
Re: Largest total uncomputable function competition
Posted: November 25th, 2019, 6:14 am
by 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.
Re: Largest total uncomputable function competition
Posted: November 25th, 2019, 6:25 am
by PkmnQ
toroidalet wrote: November 20th, 2019, 9:43 pm
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
Re: Largest total uncomputable function competition
Posted: November 25th, 2019, 9:32 am
by Moosey
PkmnQ wrote: November 25th, 2019, 6:25 am
toroidalet wrote: November 20th, 2019, 9:43 pm
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
No.
That's the pathetically tiny (by comparison) e_0
Re: Largest total uncomputable function competition
Posted: January 9th, 2020, 2:47 am
by 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
Re: Largest total uncomputable function competition
Posted: January 9th, 2020, 8:21 pm
by 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?
Re: Largest total uncomputable function competition
Posted: January 11th, 2020, 5:27 am
by testitemqlstudop
Let's say the tape manipulates reals instead of integers.