Are you allowed to write a program which calls the possible oracle as a function and which uses recursion, are you allowed to have multiple programs, and are you allowed to write to those programs? If so, I wonder if the series below would do. (I’m not going to suggest it works, until I have a few other people check it, and until I make sure that the psuedocode is understandable.)
Program A:
Call Program B;
if Possible Oracle(Program B)=”halts” then do;
Add line “Print ‘even more gibberish’ to the beginning of Program B;
Call Program A;
end if;
else if Possible Oracle(Program B)=”does not halt” then do;
print “Possible Oracle is a fake.”
end if;
End Program A.
Program B:
Print ‘even more gibberish’;
End Program B.
And then after defining all of that, run Possible Oracle(Program A);
Let’s say Possible Oracle is a 20 line fake.
It starts Running A to see if it halts.
The first time it runs through the loop in A, it runs B, which is 1 line. It then tests B, which is 1 line. It reports correctly that B halts. Based on that, it adds 1 line to B, and runs B, which is now 2 lines. It then tests B again, which is 2 lines. It reports correctly that B halts.
(Later)
Based on that, it adds 1 line to B, and runs it again. B is 21 lines. It then tests B, which is 21 lines. It reports incorrectly that B does not halt. Prints “Possible Oracle is a fake.”, and Program A ends, so it reports Program A halts. sure enough, it’s a fake.
Let’s say Possible Oracle is real.
It starts Running A to see if it halts.
The first time it runs through the loop in A, it runs B, which is 1 line. It then tests B, which is 1 line. It reports correctly that B halts. Based on that, it adds 1 line to B, and runs B, which is now 2 lines. It then tests B again, which is now 2 lines.
It reports correctly that B halts. Based on that, it adds 1 line to B, and tests it again…
(Later)
Program A, as far as I can tell, can’t halt for a true oracle.
Let’s Assume B gets to the point where it does not halt. then since Program A will run that Program B, Program A will never halt.
Let’s Assume B never gets to the point where it never halts. then since Program A calls the possible oracle, it will report that Program B halts, and if that’s the case, it calls an additional Program A instead of ending. The first Program A will never halt.
I think that should work, but unfortunately I don’t have a fake oracle and a real oracle to use for testing.
Presumably you can’t ask the oracle about the halting behavior of programs which call the oracle. Otherwise the standard proof that the halting problem is undecidable can be used to show that the oracle is fake: just have a program ask the oracle about itself, then do the opposite.
Ah, I didn’t realize that. From looking over my program again, this appears to mostly be a slightly longer algorithm that does more or less what Thomblake said earlier. I didn’t realize that was what I would end up with when I started trying to make one, but I guess it’s a standard way of looking at it.
Are you allowed to write a program which calls the possible oracle as a function and which uses recursion, are you allowed to have multiple programs, and are you allowed to write to those programs? If so, I wonder if the series below would do. (I’m not going to suggest it works, until I have a few other people check it, and until I make sure that the psuedocode is understandable.)
Program A:
Call Program B;
if Possible Oracle(Program B)=”halts” then do;
Add line “Print ‘even more gibberish’ to the beginning of Program B;
Call Program A;
end if;
else if Possible Oracle(Program B)=”does not halt” then do;
print “Possible Oracle is a fake.”
end if;
End Program A.
Program B:
Print ‘even more gibberish’;
End Program B.
And then after defining all of that, run Possible Oracle(Program A);
Let’s say Possible Oracle is a 20 line fake.
It starts Running A to see if it halts. The first time it runs through the loop in A, it runs B, which is 1 line. It then tests B, which is 1 line. It reports correctly that B halts. Based on that, it adds 1 line to B, and runs B, which is now 2 lines. It then tests B again, which is 2 lines. It reports correctly that B halts.
(Later)
Based on that, it adds 1 line to B, and runs it again. B is 21 lines. It then tests B, which is 21 lines. It reports incorrectly that B does not halt. Prints “Possible Oracle is a fake.”, and Program A ends, so it reports Program A halts. sure enough, it’s a fake.
Let’s say Possible Oracle is real.
It starts Running A to see if it halts. The first time it runs through the loop in A, it runs B, which is 1 line. It then tests B, which is 1 line. It reports correctly that B halts. Based on that, it adds 1 line to B, and runs B, which is now 2 lines. It then tests B again, which is now 2 lines. It reports correctly that B halts. Based on that, it adds 1 line to B, and tests it again…
(Later)
Program A, as far as I can tell, can’t halt for a true oracle.
Let’s Assume B gets to the point where it does not halt. then since Program A will run that Program B, Program A will never halt.
Let’s Assume B never gets to the point where it never halts. then since Program A calls the possible oracle, it will report that Program B halts, and if that’s the case, it calls an additional Program A instead of ending. The first Program A will never halt.
I think that should work, but unfortunately I don’t have a fake oracle and a real oracle to use for testing.
Edit: Fixed line breaks
Presumably you can’t ask the oracle about the halting behavior of programs which call the oracle. Otherwise the standard proof that the halting problem is undecidable can be used to show that the oracle is fake: just have a program ask the oracle about itself, then do the opposite.
Ah, I didn’t realize that. From looking over my program again, this appears to mostly be a slightly longer algorithm that does more or less what Thomblake said earlier. I didn’t realize that was what I would end up with when I started trying to make one, but I guess it’s a standard way of looking at it.