Suppose I pass you the bit that says the candidate does not halt, followed by an infinite string of 1s. Then to decode this (by which I mean reject it as invalid) you would need to know whether the busy beaver candidate halts, which we’ve rejected as hard.
This is a problem with the Sphinxes, too, in retrospect. A Hollow Sphinx could just keep answering “yes” if it’s hard to check whether the Turing machine halts, making you do the hard work.
Agreed, but a non-oracle Sphinx wouldn’t be impossible to recognize any more, it would just be very hard to recognize (you would need the Sphinx to guess wrong, and to be patient enough to figure out that it did).
In summary, whoever has the halting oracle wins, and if nobody does, it’s a patience contest.
Suppose I pass you the bit that says the candidate does not halt, followed by an infinite string of 1s. Then to decode this (by which I mean reject it as invalid) you would need to know whether the busy beaver candidate halts, which we’ve rejected as hard.
This is a problem with the Sphinxes, too, in retrospect. A Hollow Sphinx could just keep answering “yes” if it’s hard to check whether the Turing machine halts, making you do the hard work.
Agreed, but a non-oracle Sphinx wouldn’t be impossible to recognize any more, it would just be very hard to recognize (you would need the Sphinx to guess wrong, and to be patient enough to figure out that it did).
In summary, whoever has the halting oracle wins, and if nobody does, it’s a patience contest.