In the Atlas Mountains, one can meet two species of Sphinxes: True Sphinxes and Hollow Sphinxes. Each True Sphinx has a secret number, and it will truthfully answer any question about it, provided it can do so in less than a hundred words. A Hollow Sphinx, however, just enjoys wasting people’s time : it has no secret number but will pretend it does, and answers questions so as to never contradict itself and maintain uncertainty in the asker’s mind.
While you can be sure you are speaking to a True Sphinx (for example, by guessing it’s number), you can never be sure that you are speaking to a Hollow Sphinx—it might be a True Sphinx whose number is very large. In fact, no-one has been able to determine whether any Hollow Sphinxes still exist.
Seems that the best strategy would “merely” be to try to find an upper bound, like “Is the number smaller than “BusyBeaver(BusyBeaver(BusyBeaver(BusyBeaver(3^^^3))))?”, and a Hollow Sphinx would just answer “no, it’s bigger”, so presented like that, it doesn’t look like a very interesting problem.
Though there may be a series of question such that a Hollow Sphinx can’t keep up the masquarade unless it has a Halting Oracle (say, a yes-or-no question such that it can’t compute which answer could apply to an infinite amount of numbers), but I have no idea which questions those might be.
(The same applies to the original problem: there might be some exotic encoding such that an “infinitely confusing” input exists, determining say it’s first 100 bits is uncomputable.)
This is the moral equivalent of saying BB(3^^^3)+1. Mere recursion is puny. At least jump from BB to BB_2!
determining say it’s first 100 bits is uncomputable
Every sequence of 100 bits is computable.
Here’s an encoding where the “infinitely confusing” input is uncomputable: take the unary encoding from my post and XOR it with some infinite uncomputable sequence, e.g. the halting oracle sequence. Unfortunately, you can’t use this test in practice because you can’t compute the required bits either.
Mere recursion may be puny, but given the “fifteen-second challenge” and that BB_2 etc aren’t well known enough to use there, it seems like the best bet, doesn’t it?
To put it more formally: we want an encoding algorithm E and a decoding algorithm D such that for any natural number n, a turing machine can compute E(n) and D(E(n)) in finite time, but that there exists a k such that “determining a string s of length k so that the set {n such that E(n) starts with s} is infinite” is an undecidable problem. Do D and E exist fulfilling those conditions?
I admit my working knowledge of what is decidable/computable is somewhat limited; maybe the condition should be to find E and D such that no algorithm can return s given k, or whether there exists an algorithm that given E and D, can return a “confusing” sequence of arbitrary length.
I think I have a partial solution for the case where the “infinitely confusing” string is unique. Namely, if there is a unique infinite string S on which D doesn’t terminate, then S is computable.
Here’s an algorithm for computing S by using D. Assume that the first bit of S is 0. That means D terminates on all strings whose first bit is 1. By the argument from the original post, that implies D’s running time on strings starting with 1 is uniformly bounded. (Otherwise we would be able to generate an “infinitely confusing” string for D that starts with 1 by using the proof technique from my post, which can’t happen because S is unique and starts with 0 by assumption.) Therefore, by feeding D all possible finite inputs in turn while allowing it gradually increasing running times (“dovetailing”), we will eventually get a “covering set” that proves D always terminates on strings starting with 1. So we determine that the first bit of S must be 0. In the same way you can determine the second bit of S, and so on.
Let’s see how it works on unary notation. We run D on all finite inputs in turn. First we notice that D(“0”) terminates without trying to read further, therefore the first bit of S is 1. Then we notice that D(“10″) terminates, therefore the second bit of S is also 1. And so on.
I’m sorry to ask this question, because it seems very stupid, but how exactly would one create a set-up where a Turing machine, as in head-and-tape style thing, actually interacts with a halting oracle?
I don’t doubt that its possible but I can’t think of an elegant way to do it.
Ahh, so that’s what the <Can someone recall the title of Eliezer’s parable in which the genius level humans spend thousands of years deciphering the messages sent by the not-so-smart universe simulators?> were using!
<Can someone recall the title of Eliezer’s parable in which the genius level humans spend thousands of years deciphering the messages sent by the not-so-smart universe simulators?>
You may be thinking of “That Alien Message.” Best wishes, the Less Wrong Reference Desk.
True, but it would still yield an interesting answer :)
ETA: Also, one could give the sphinx a Turing machine and ask if it halts within N steps or fewer, where N is that sphinx’s number. After a number of such questions, you’d feel pretty confident that either the sphinx is a True Sphinx or it has a halting oracle.
So to bring it back to cousin_it’s post, one could have a “busy beaver candidate” (a turing machines where we don’t know whether it goes on for ever or eventually halt or start repeating), and the encoding of a natural number n would be that the first bit is whether or not that candidate halts before n steps, followed by the unary encoding of n.
“Encoding” or decoding n would be easy (but long when n is big), but “breaking” that encoding for any usy beaver candidate would require a halting oracle.
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.
An alternative phrasing:
I wonder if your explanation will make sense to people who didn’t understand the original problem… but it’s awesome!
Seems that the best strategy would “merely” be to try to find an upper bound, like “Is the number smaller than “BusyBeaver(BusyBeaver(BusyBeaver(BusyBeaver(3^^^3))))?”, and a Hollow Sphinx would just answer “no, it’s bigger”, so presented like that, it doesn’t look like a very interesting problem.
Though there may be a series of question such that a Hollow Sphinx can’t keep up the masquarade unless it has a Halting Oracle (say, a yes-or-no question such that it can’t compute which answer could apply to an infinite amount of numbers), but I have no idea which questions those might be.
(The same applies to the original problem: there might be some exotic encoding such that an “infinitely confusing” input exists, determining say it’s first 100 bits is uncomputable.)
This is the moral equivalent of saying BB(3^^^3)+1. Mere recursion is puny. At least jump from BB to BB_2!
Every sequence of 100 bits is computable.
Here’s an encoding where the “infinitely confusing” input is uncomputable: take the unary encoding from my post and XOR it with some infinite uncomputable sequence, e.g. the halting oracle sequence. Unfortunately, you can’t use this test in practice because you can’t compute the required bits either.
Mere recursion may be puny, but given the “fifteen-second challenge” and that BB_2 etc aren’t well known enough to use there, it seems like the best bet, doesn’t it?
If you’re okay with losing to me, then it’s a good bet, yeah :-)
To put it more formally: we want an encoding algorithm E and a decoding algorithm D such that for any natural number n, a turing machine can compute E(n) and D(E(n)) in finite time, but that there exists a k such that “determining a string s of length k so that the set {n such that E(n) starts with s} is infinite” is an undecidable problem. Do D and E exist fulfilling those conditions?
I admit my working knowledge of what is decidable/computable is somewhat limited; maybe the condition should be to find E and D such that no algorithm can return s given k, or whether there exists an algorithm that given E and D, can return a “confusing” sequence of arbitrary length.
I asked MathOverflow to solve this and got a complete solution within an hour. Just like last time. Wow, just wow.
The stack exchange sites are pretty impressing, and humbling. Maybe Eliezer should outsource more of his research to them.
I think I have a partial solution for the case where the “infinitely confusing” string is unique. Namely, if there is a unique infinite string S on which D doesn’t terminate, then S is computable.
Here’s an algorithm for computing S by using D. Assume that the first bit of S is 0. That means D terminates on all strings whose first bit is 1. By the argument from the original post, that implies D’s running time on strings starting with 1 is uniformly bounded. (Otherwise we would be able to generate an “infinitely confusing” string for D that starts with 1 by using the proof technique from my post, which can’t happen because S is unique and starts with 0 by assumption.) Therefore, by feeding D all possible finite inputs in turn while allowing it gradually increasing running times (“dovetailing”), we will eventually get a “covering set” that proves D always terminates on strings starting with 1. So we determine that the first bit of S must be 0. In the same way you can determine the second bit of S, and so on.
Let’s see how it works on unary notation. We run D on all finite inputs in turn. First we notice that D(“0”) terminates without trying to read further, therefore the first bit of S is 1. Then we notice that D(“10″) terminates, therefore the second bit of S is also 1. And so on.
That looks true, though the process you describe only works if S is indeed unique, othwerwise it gets stuck.
BB_2?
The BusyBeaver function for Turing machines with a halting oracle.
Aaronson
I’m sorry to ask this question, because it seems very stupid, but how exactly would one create a set-up where a Turing machine, as in head-and-tape style thing, actually interacts with a halting oracle?
I don’t doubt that its possible but I can’t think of an elegant way to do it.
Wikipedia has a detailed explanation of the setup.
Ahh, so that’s what the <Can someone recall the title of Eliezer’s parable in which the genius level humans spend thousands of years deciphering the messages sent by the not-so-smart universe simulators?> were using!
You may be thinking of “That Alien Message.” Best wishes, the Less Wrong Reference Desk.
Thankyou! I’d been looking for that one for a while.
Try asking the sphinx “Is your number less than 10 if and only if P=NP?”
That wouldn’t work for distinguishing the two kinds of sphinxes, unless you suppose that one kind knows whether P=NP and the other doesn’t.
True, but it would still yield an interesting answer :)
ETA: Also, one could give the sphinx a Turing machine and ask if it halts within N steps or fewer, where N is that sphinx’s number. After a number of such questions, you’d feel pretty confident that either the sphinx is a True Sphinx or it has a halting oracle.
Huh, that looks like it could work, neat :)
So to bring it back to cousin_it’s post, one could have a “busy beaver candidate” (a turing machines where we don’t know whether it goes on for ever or eventually halt or start repeating), and the encoding of a natural number n would be that the first bit is whether or not that candidate halts before n steps, followed by the unary encoding of n.
“Encoding” or decoding n would be easy (but long when n is big), but “breaking” that encoding for any usy beaver candidate would require a halting oracle.
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.