I think I can win Game 1 against almost anyone—in other words, I think I have a larger computable number than any sort of computable number I’ve seen anyone describe in these sorts of contests, where the top entries typically use the fast-growing hierarchy for large recursive ordinals, in contests where Busy Beaver and beyond aren’t allowed.
Game 2 is interesting. My first thought was that running the other person’s program and adding 1 to the result guarantees that they die—either their program doesn’t halt, or your program is larger. So my first thought was that it just reduced to 3 players who can choose whether to kill each other or not, at least 2 of whom have to die, with no solution except from TDT-type correlations. But suppose I output a large number without looking at my opponents’ code, and my opponents both try to run the other two programs and add the outputs together, plus 1. They both go into an infinite loop and I win. There may be some nontrivial Nash-style equilibrium to be found here.
I think I can win Game 1 against almost anyone—in other words, I think I have a larger computable number than any sort of computable number I’ve seen anyone describe in these sorts of contests, where the top entries typically use the fast-growing hierarchy for large recursive ordinals, in contests where Busy Beaver and beyond aren’t allowed.
Okay I have to ask. Care to provide a brief description? You can assume familiarity with all the standard tricks if that helps.
I suspect that TREE(3) is the number he’s referring to, since I’ve seen it mentioned on LW a few times, and it seems to be larger than most other numbers that are considered notable for their largeness.
Of course, it’s easy to come up with a number larger than TREE(3).
As far as I know, the TREE function has no particular relationship to the busy beaver functions. The TREE function is computable, whereas the busy beaver functions are not.
I wonder how TREE(3) compares to Loader’s number. If I understand correctly, if Kruskal’s tree theorem can be proved in the calculus of constructions using a reasonable number of symbols (where 3^^^3 counts as a reasonable number, but TREE(3) does not), then Loader’s number is much larger.
Edit: Wikipedia states that Friedman’s special cases of Kruskal’s tree theorem can “easily” be proved in second-order arithmetic, which can be expressed in the calculus of constructions. I’m pretty sure this means that the TREE function can be written in the calculus of constructions using a reasonable number of symbols, meaning that Loader’s number is much larger than TREE(n) for any reasonable value of n.
And speaking of which, what kind of big number contest bans busy beaver? Srsly : <
A computable one. OP is not clear how his hypercomputer is solving the halting problem—does it have a ‘halts(s)’ function for programs that do not use ‘halts’ function, or what. The solution 2 in the OP is pretty much equivalent to the busy beaver, and it can not be done without use of halting oracle because some of those programs would loop forever, making the final print statement unreachable.
How does your proposed solution for Game 1 stack up against the brute-force metastrategy?
Game 2 is a bit tricky. An answer to your described strategy would be to write a large number generator f(1),which produces some R, which does not depend on your opponents’ programs, create a virtual machine that runs your opponents’ programs for r steps, and, if they haven’t halted, swaps the final recursive entry on the call stack with some number (say, R, for simplicity), and iterates upwards to produce real numbers for their function values. Then you just return the max of all three values. This strategy wins against any naive strategy, wins if your opponents are stuck in infinite loops, and, if taken by all players symmetrically, reduces the game to who has a larger R—i.e. the game simplifies to GAME1, and there is still (probably) one survivor.
How does your proposed solution for Game 1 stack up against the brute-force metastrategy?
Well the brute force strategy is going to do a lot better, because it’s pretty easy to come up with a number bigger than the length of the longest program anyone has ever thought to write, and then plugging that into your brute force strategy automatically beats any specific program that anyone has ever thought to write. On the other hand, the meta-strategy isn’t actually computable (you need to be able to decide whether program produces large outputs, which requires a halting oracle or at least a way of coming up with large stopping times to test against). So it doesn’t really make sense to compare them.
I think I can win Game 1 against almost anyone—in other words, I think I have a larger computable number than any sort of computable number I’ve seen anyone describe in these sorts of contests, where the top entries typically use the fast-growing hierarchy for large recursive ordinals, in contests where Busy Beaver and beyond aren’t allowed.
Game 2 is interesting. My first thought was that running the other person’s program and adding 1 to the result guarantees that they die—either their program doesn’t halt, or your program is larger. So my first thought was that it just reduced to 3 players who can choose whether to kill each other or not, at least 2 of whom have to die, with no solution except from TDT-type correlations. But suppose I output a large number without looking at my opponents’ code, and my opponents both try to run the other two programs and add the outputs together, plus 1. They both go into an infinite loop and I win. There may be some nontrivial Nash-style equilibrium to be found here.
Okay I have to ask. Care to provide a brief description? You can assume familiarity with all the standard tricks if that helps.
I suspect that TREE(3) is the number he’s referring to, since I’ve seen it mentioned on LW a few times, and it seems to be larger than most other numbers that are considered notable for their largeness.
Of course, it’s easy to come up with a number larger than TREE(3).
I dunno, is that tree sequence related to the busy beaver sequence? And speaking of which, what kind of big number contest bans busy beaver? Srsly : <
As far as I know, the TREE function has no particular relationship to the busy beaver functions. The TREE function is computable, whereas the busy beaver functions are not.
I wonder how TREE(3) compares to Loader’s number. If I understand correctly, if Kruskal’s tree theorem can be proved in the calculus of constructions using a reasonable number of symbols (where 3^^^3 counts as a reasonable number, but TREE(3) does not), then Loader’s number is much larger.
Edit: Wikipedia states that Friedman’s special cases of Kruskal’s tree theorem can “easily” be proved in second-order arithmetic, which can be expressed in the calculus of constructions. I’m pretty sure this means that the TREE function can be written in the calculus of constructions using a reasonable number of symbols, meaning that Loader’s number is much larger than TREE(n) for any reasonable value of n.
A computable one. OP is not clear how his hypercomputer is solving the halting problem—does it have a ‘halts(s)’ function for programs that do not use ‘halts’ function, or what. The solution 2 in the OP is pretty much equivalent to the busy beaver, and it can not be done without use of halting oracle because some of those programs would loop forever, making the final print statement unreachable.
Yup, that makes sense.
How does your proposed solution for Game 1 stack up against the brute-force metastrategy?
Game 2 is a bit tricky. An answer to your described strategy would be to write a large number generator f(1),which produces some R, which does not depend on your opponents’ programs, create a virtual machine that runs your opponents’ programs for r steps, and, if they haven’t halted, swaps the final recursive entry on the call stack with some number (say, R, for simplicity), and iterates upwards to produce real numbers for their function values. Then you just return the max of all three values. This strategy wins against any naive strategy, wins if your opponents are stuck in infinite loops, and, if taken by all players symmetrically, reduces the game to who has a larger R—i.e. the game simplifies to GAME1, and there is still (probably) one survivor.
Well the brute force strategy is going to do a lot better, because it’s pretty easy to come up with a number bigger than the length of the longest program anyone has ever thought to write, and then plugging that into your brute force strategy automatically beats any specific program that anyone has ever thought to write. On the other hand, the meta-strategy isn’t actually computable (you need to be able to decide whether program produces large outputs, which requires a halting oracle or at least a way of coming up with large stopping times to test against). So it doesn’t really make sense to compare them.