So, there are actually compelling reasons that halting oracles can’t actually exist. Quite aside from your solution, it’s straightforward to write programs with undefined behavior. Ex:
function undef():
if ORACLE_HALT(undef)::
while 1 != 2:
print "looping forever"
else:
print "halting"
return 0
For the sake of the gdanken-experiment, can we just assume that Omega has a well-established policy of horribly killing tricky people who try to set up recursive hypercomputational functions whose halting behavior depends on their own halting behavior?
For the sake of the gdanken-experiment, can we just assume that Omega has a well-established policy of horribly killing tricky people who try to set up recursive hypercomputational functions whose halting behavior depends on their own halting behavior?
Oh, yes please, that makes it easy.
if (halt(other_player_1)) do_not_halt();
if (halt(other_player_2)) do_not_halt();
return 0;
At least in GAME3 this kills off the clever opponents who try to simulate me.
Does the problem have a time limit? Does the computer you use to write your program have any storage limits? For a non-tricky answer I think the only solution is to repeatedly apply the busy beaver function BB as many times as physically possible before you fall over from exhaustion. You have to be fairly clever about it; first write a macro expander and then run that for as long as possible recursively expanding bb(X) on X = bb(some-big-number). Submit the result when it’s physically impossible to continue expanding the macro.
Actually, this can be improved if the lower limit is the length of program that you can submit. Assume there is a maximum of N bits that you can submit. If you have hypercomputation locally available then just find a particular solution to bb(N) and submit it. If you do not have hypercomputation locally available then you have to try your best at writing a solution to bb(N). The solution in the first paragraph is not bad as a starting point, and in fact I was silly and didn’t realize I was trying to approximate bb(N) and actually spent some time thinking of other strategies that beat it. The basic idea is to realize that every solution is (probably!) going to be roughly of the form F(G()) = return BB^G()(3), where G() is the largest function you can think of that fits in the remaining bits. If the notation is confusing, I mean bb(bb(bb … bb(3) .. ))) as many times as G() returns. Naively I thought that meant I could just treat G() as a sub-problem of the form G(H()) = BB^H()(3) and so on until I ran out of bits. But that can be composed into a meta-function of F(G()) = BB^(BB^H()(3)) = BB^^H()(3). And then BB^^^^^...^^^^H()(3) with H() up-arrows as a meta-meta-solution. Presumably there is a meta-function for that process as well, and so on, meta-function piled upon meta-function. So that means there is probably a procedure to derive new meta-functions and you should just run that derivation procedure until you find a sufficiently large meta-function and apply it. In this case, there is no sufficiently large meta-function because the derivation function would run on Omega’s hypercomputer with arbitrary precision. So you’d have to find some way to interrupt the meta-function derivation using however many of the remaining N bits you have left. Oh, but that is a meta-meta-function that should stop deriving meta-functions after the biggest number you can specify which is the subproblem we were trying to solve in the first place. So the meta-meta-meta-program can derive as many meta-meta-programs as possible with the bits left… I think (somewhat weakly) that at some point this particular chain of metas will exhaust the number of bits in N. But perhaps there is an Omega-function that can easily handle any number of meta-extensions and we have to limit the resulting Omega-Omega-function...
In short, I think a limited number of bits in the submission combined with the inability to locally hypercompute yields the most interesting situation by far (build your own bb(N)!). Being able to locally hypercompute and having a limited submission length is trivial. Having an unbounded submission length falls, I think, to the nested bb() approach unless you can relatively quickly write a meta-strategy and start repeatedly expanding that while you work on an omega-strategy, etc. using roughly the same strategy as the limited length submission without hypercomputing approach, until you start to mentally deteriorate significantly. At that point you better submit your best result before you make a non-halting mistake in your senility or from potential illness or injury.
Of course if Omega sticks you in a room with infinite food and toiletries and time and health then why bother submitting a program?
So, there are actually compelling reasons that halting oracles can’t actually exist. Quite aside from your solution, it’s straightforward to write programs with undefined behavior. Ex:
function undef():
For the sake of the gdanken-experiment, can we just assume that Omega has a well-established policy of horribly killing tricky people who try to set up recursive hypercomputational functions whose halting behavior depends on their own halting behavior?
Oh, yes please, that makes it easy.
if (halt(other_player_1)) do_not_halt(); if (halt(other_player_2)) do_not_halt(); return 0;
At least in GAME3 this kills off the clever opponents who try to simulate me.
That would definitely make you one of those tricky people.
Does the problem have a time limit? Does the computer you use to write your program have any storage limits? For a non-tricky answer I think the only solution is to repeatedly apply the busy beaver function BB as many times as physically possible before you fall over from exhaustion. You have to be fairly clever about it; first write a macro expander and then run that for as long as possible recursively expanding bb(X) on X = bb(some-big-number). Submit the result when it’s physically impossible to continue expanding the macro.
Actually, this can be improved if the lower limit is the length of program that you can submit. Assume there is a maximum of N bits that you can submit. If you have hypercomputation locally available then just find a particular solution to bb(N) and submit it. If you do not have hypercomputation locally available then you have to try your best at writing a solution to bb(N). The solution in the first paragraph is not bad as a starting point, and in fact I was silly and didn’t realize I was trying to approximate bb(N) and actually spent some time thinking of other strategies that beat it. The basic idea is to realize that every solution is (probably!) going to be roughly of the form F(G()) = return BB^G()(3), where G() is the largest function you can think of that fits in the remaining bits. If the notation is confusing, I mean bb(bb(bb … bb(3) .. ))) as many times as G() returns. Naively I thought that meant I could just treat G() as a sub-problem of the form G(H()) = BB^H()(3) and so on until I ran out of bits. But that can be composed into a meta-function of F(G()) = BB^(BB^H()(3)) = BB^^H()(3). And then BB^^^^^...^^^^H()(3) with H() up-arrows as a meta-meta-solution. Presumably there is a meta-function for that process as well, and so on, meta-function piled upon meta-function. So that means there is probably a procedure to derive new meta-functions and you should just run that derivation procedure until you find a sufficiently large meta-function and apply it. In this case, there is no sufficiently large meta-function because the derivation function would run on Omega’s hypercomputer with arbitrary precision. So you’d have to find some way to interrupt the meta-function derivation using however many of the remaining N bits you have left. Oh, but that is a meta-meta-function that should stop deriving meta-functions after the biggest number you can specify which is the subproblem we were trying to solve in the first place. So the meta-meta-meta-program can derive as many meta-meta-programs as possible with the bits left… I think (somewhat weakly) that at some point this particular chain of metas will exhaust the number of bits in N. But perhaps there is an Omega-function that can easily handle any number of meta-extensions and we have to limit the resulting Omega-Omega-function...
In short, I think a limited number of bits in the submission combined with the inability to locally hypercompute yields the most interesting situation by far (build your own bb(N)!). Being able to locally hypercompute and having a limited submission length is trivial. Having an unbounded submission length falls, I think, to the nested bb() approach unless you can relatively quickly write a meta-strategy and start repeatedly expanding that while you work on an omega-strategy, etc. using roughly the same strategy as the limited length submission without hypercomputing approach, until you start to mentally deteriorate significantly. At that point you better submit your best result before you make a non-halting mistake in your senility or from potential illness or injury.
Of course if Omega sticks you in a room with infinite food and toiletries and time and health then why bother submitting a program?