Game 1, solution 2 would not work as I understand it. Because some of the programs that you generate will not terminate, and so your program wouldn’t terminate either. Omega can detect that, but your program can’t.
Game 4 is also interesting, precisely because it actually has a non-zero probability of happening, I don’t believe Omega exists, and I doubt the existence hypercomputers even more. So if I were to find myself in such a game situation, I would think that it is more likely to be scenario 4 than to be 3.
The room function take an argument of a string (which controls the text printed on the wall, and outputs whatever number the person in the simulation’s program returns)
The person doesn’t return a number, the person returns a computer program. Or are you saying it returns the number that will be output by that program? What happens if that program doesn’t terminate? If you say that the room function returns no output (but does terminate), then running such a program requires a halting oracle. And then running a program that calls the room function requires a halting+1 oracle (oracle of halting +1?). Which means that Omega needs a halting+ω oracle!
So I guess I should have specified which model of hypercomputation Omega is using. Omega’s computer can resolve ANY infinite trawl in constant time (assume time travel and an enormous bucket of phlebotinum is involved) - including programs which generate programs. So, the players also have the power to resolve any infinite computation in constant time. Were they feeling charitable, in an average utilitarian sense, they could add a parasitic clause to their program that simply created a few million copies of themselves which would work together to implement FAI, allow the FAI to reverse-engineer humanity by talking to all three of the contestants, then creating arbitrarily large numbers of value-fulfilled people and simulating them forever. But I digress.
In short, take it as a given that anyone, on any level, has a halting oracle for arbitrary programs, subprograms, and metaprograms, and that non-returning programs are treated as producing no output.
I don’t think players actually have hypercomputational abilities otherwise they could do the following:
function self(param n)
{
if (hypercompute(self(n)) != 0) return hypercompute(self(n+1));
return n;
}
self(1);
If the recursive function self(n) would not halt for some n then the player’s program would halt and return a value < n. But in that case it would halt for self(n) and return a value larger than n. So it must eventually halt and return The Largest Integer.
I assume you just mean that any program the players write will either halt or not and only Omega will know for sure if it doesn’t halt.
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?
In short, take it as a given that anyone, on any level, has a halting oracle for arbitrary programs, subprograms, and metaprograms, and that non-returning programs are treated as producing no output.
In this case, I have no desire to escape from the room.
Actually, my secret preferred solution to GAME3 is to immediately give up, write a program that uses all of us working together for arbitrary amounts of time (possibly with periodic archival and resets to avoid senescence and insanity), to create an FAI, then plugging our minds into an infinite looping function in which the FAI makes a universe for us, populates it with agreeable people, and fulfills all of our values forever. Program never halts, return value is taken to be 0, Niger0 is instantly and painlessly killed, and Niger1 (the simulation) eventually gets to go live in paradise for eternity.
Game 1, solution 2 would not work as I understand it. Because some of the programs that you generate will not terminate, and so your program wouldn’t terminate either. Omega can detect that, but your program can’t.
Game 4 is also interesting, precisely because it actually has a non-zero probability of happening, I don’t believe Omega exists, and I doubt the existence hypercomputers even more. So if I were to find myself in such a game situation, I would think that it is more likely to be scenario 4 than to be 3.
The person doesn’t return a number, the person returns a computer program. Or are you saying it returns the number that will be output by that program? What happens if that program doesn’t terminate? If you say that the room function returns no output (but does terminate), then running such a program requires a halting oracle. And then running a program that calls the room function requires a halting+1 oracle (oracle of halting +1?). Which means that Omega needs a halting+ω oracle!
So I guess I should have specified which model of hypercomputation Omega is using. Omega’s computer can resolve ANY infinite trawl in constant time (assume time travel and an enormous bucket of phlebotinum is involved) - including programs which generate programs. So, the players also have the power to resolve any infinite computation in constant time. Were they feeling charitable, in an average utilitarian sense, they could add a parasitic clause to their program that simply created a few million copies of themselves which would work together to implement FAI, allow the FAI to reverse-engineer humanity by talking to all three of the contestants, then creating arbitrarily large numbers of value-fulfilled people and simulating them forever. But I digress.
In short, take it as a given that anyone, on any level, has a halting oracle for arbitrary programs, subprograms, and metaprograms, and that non-returning programs are treated as producing no output.
I don’t think players actually have hypercomputational abilities otherwise they could do the following:
function self(param n) { if (hypercompute(self(n)) != 0) return hypercompute(self(n+1)); return n; }
self(1);
If the recursive function self(n) would not halt for some n then the player’s program would halt and return a value < n. But in that case it would halt for self(n) and return a value larger than n. So it must eventually halt and return The Largest Integer.
I assume you just mean that any program the players write will either halt or not and only Omega will know for sure if it doesn’t halt.
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?
In this case, I have no desire to escape from the room.
That’s fair.
Actually, my secret preferred solution to GAME3 is to immediately give up, write a program that uses all of us working together for arbitrary amounts of time (possibly with periodic archival and resets to avoid senescence and insanity), to create an FAI, then plugging our minds into an infinite looping function in which the FAI makes a universe for us, populates it with agreeable people, and fulfills all of our values forever. Program never halts, return value is taken to be 0, Niger0 is instantly and painlessly killed, and Niger1 (the simulation) eventually gets to go live in paradise for eternity.