What would you ask an all powerful alien?

Carl Sagan was one of the greatest popularizer of science in general, and astronomy and astrophysics in particular. He became world famous for his many books, his award winning TV series, and his novel “Contact,” which was the basis for the film starring Jodie Foster.

Today I want to talk about a lunch or dinner time conversation that I have had many times—often at conferences. The question is what would you ask an all powerful alien?

Sagan often talked about contact with aliens from advanced civilizations. He once wrote:

It’s a stimulating exercise to think of questions to which no human today knows the answers, but where a correct answer would immediately be recognized as such. It’s even more challenging to formulate such questions in fields other than mathematics. Perhaps we should hold a contest and collect the best responses in “Ten Questions to Ask an Alien.”

I thought it would be interesting to discuss asking question to an alien. I want to mention the work of Brendan Juba and Madhu Sudan, where they discuss a different issue—how would you communicate with an alien who does not speak the same language as you do. Perhaps I will discuss their interesting work another time.

The Problem

Suppose that an all knowing being, perhaps from another world, arrives on Earth. Let’s agree to call her Vina—a name from Star Trek. She knows everything and is always truthful, a pretty neat combination in anyone. She tells you that you will get to ask her exactly one question. What would you ask?

For those of you who are Simpsons fans, you may recall the episode where Apu and Homer meet the all knowing head and master of Kwik-E-Mart. Apu and Homer are told they will get to ask three questions, not just one. The conversation goes like this:

Master: Approach, my sons. [they do] You may ask me three questions.
Apu: That’s great, because all I need is one —
Homer: Are you really the head of the Kwik-E-Mart?
Master: Yes.
Homer: Really?
Master: Yes.
Homer: You?
Master: Yes. I hope this has been enlightening for you.
Apu: But I must —
Master: Thank you, come again.
Apu: But —
Master: Thank you, come again.

Our job, which should not be hard, is to make better use of our one question, than Homer did of his three questions.

Solutions

So what should we ask Vina? Since we are mathematically oriented when we have discussed this question we often hear people say they would ask: Is P not equal to NP? Usually someone quickly points out that they are pretty sure that is true, so why not ask: Is P${\neq}$ NP true and is the Riemann Hypothesis true? All agree this is a pretty clever idea, until someone points out there is a danger that she could answer no. In which case we have some information, but we do not know anything for sure. So is this a good idea or not?

Solutions With Randomization

Suppose we are allowed to ask Vina questions that are probabilistic. What about a question like:

Vina, please flip a fair coin. If it is heads answer yes/no for P=NP? If it is tails then answer yes/no for the Riemann Hypothesis.

My first thought was that this question was really the same as the previous question, but that is not quite right. Let ${A}$ be the statement “P${\neq}$NP is true” and let ${B}$ be the statement that the “Riemann Hypothesis is true.” The question we asked before was

$\displaystyle A \ \mathrm{and} \ B.$

The new question is: flip a fair coin, if it is heads answer ${A}$; if it is tails answer ${B}$.

In the non-probabilistic question a yes means that both ${A}$ and ${B}$ are true; a no means that at least one is false. In the probabilistic question a yes means that ${A}$ or ${B}$ is true; a no means that at least one is false. These are clearly different.

What happens if we allow more complex probabilistic questions. Are there reasons, advantages, to ask questions that involve Vina flipping coins? The point is we can only get one bit, so how can we use that bit to get the most information possible? Do we want to be sure about things, or do we want to simply increase our understand a bit—bad pun.

I think the formal question is what is the best use of the one question given our prior beliefs in the probability that each statement is true. Thus, let ${S_1,\dots,S_m}$ be statements, and let us believe that ${S_i}$ is true with some probability ${p_i}$. What is our best question to ask Vina to maximize our increase in information?

I am not sure the question is completely specified. Do we also need to know the joint distribution of our beliefs about all the statements?

Open Problems

What would you ask? Clearly that is not a question you can ask Vina—she only gives one bit. Suppose you thought P${\neq}$NP and Riemann and other questions were 90% likely to be true. You might ask her a question like:

Are (P${\neq}$NP & Riemann & Goldbach & Collatz & Jacobian & Twin Prime) all true?

Is this a good idea? Perhaps the questions are all 90%, but are they independent?

Also what happens if several questions are allowed? What is the best way to use the extra bits? Do we use an adaptive method or can we ask all in one question at once? Also how much does having Vina be able to use randomness help us?

October 11, 2010 1:49 pm

Wonderful question.

As a fellow Sagan admirer, I might mention a connection to another recent discussion at this blog – regarding drug use. Sagan’s famous article on his regular use of cannabis is worth revisiting. (Sagan found that it increased his creativity and problem-solving ability and had none of the drawbacks of drugs like alcohol or speed. Of course many people are surprised that cannabis can have that effect, but that’s because most common varieties are on the indica end rather than the sativa end of the spectrum – I imagine Sagan used the latter.)

2. October 11, 2010 1:51 pm

I don’t understand why we are only allowed one bit if we can only ask one question. Isn’t “Will you please show me a proof of P =/= NP?” not a question? If Vina knows everything, she will show a proof that will be verifiable (because she knows everything and only tells the truth, so she knows a verifiable proof). If she says “I can’t,” we know automatically that P=NP….

October 11, 2010 1:53 pm

I can’t recall who said the following: as we’re pretty sure that P\neq NP, we’d better ask if the first bit of the shortest proof for P\neq NP is 1. Still, this looks like a pretty desperate question! (Plus, the “no” answer could mean either that P=NP or that the first bit is 0.)

October 11, 2010 1:53 pm

This issue is related to “The Paradox of the Question” discussed by philosophers, in which the restriction to one bit is removed. See http://myweb.facstaff.wwu.edu/nmarkos/Papers/PQ.pdf

October 13, 2010 12:34 pm

That’s very amusing.

Would the solution be to adjust the question to include only non-metalogical answers, or include “all questions but this one” in Q4?

Is there any more discussion on this? Its very interesting.

October 11, 2010 2:13 pm

Another interesting thought would be what she would respond if P!=NP has no solution. Yes and no don’t cut it there, and if she were allowed to answer “no solution” (or “that is ill formed”) in that case, then we would get even more information for free.

If she responds “I don’t know”, then either the advanced civilization cannot solve it (in which case, do we give up on it?) or it has been solved as “no solution”.

In a more practical sense, asking “Does P!=NP have a solution that our civilization can find” would be something I’d be more willing to ask. “Yes” would mean that we still would not have the solution, but can be enthusiastic knowing that it will indeed one day be found by us. This would also be much more rewarding to our civilization as a whole. Then again, “no” would tell us to simply move on, since either there is no solution, or there is but we can never quite reach it in any feasible amount of time.

Or being more general, “Does at least one of P!=NP or the Riemann Hypothesis have a solution that our civilization can find?” This is still practical in that we can either eliminate both problems from our TODO lists, or know we can solve at least one of them. Eventually. When that happens, we’ll still not be sure about the second solution’s existence, but at least we’ll have an enormous breakthrough, leaving us still better off than we are today.

October 11, 2010 2:13 pm

Also what happens if several questions are allowed?

If N questions are allowed, the first could be – what are the best N-1 questions to ask you?

Since Vina is all-knowing, she even knows what “best” means to us.

—-

I don’t know if this counts as two questions or one – “Vina, If I were to ask you the best possible question, what would the question be and how would you answer it?”

October 11, 2010 2:25 pm

What’s the ordered pair of the best question that we could ask and the answer to that question?

October 11, 2010 2:56 pm

use the pcp theorem to ask about a received word in a code that encodes several interesting things. if you’re very careful, you could potentially learn a lot about several problems at once. this assumes that you can ask very long, very complicated questions. but presumably, “all knowing” covers this. this is if you can query multiple bits.

i think that “is P=NP?” isn’t the best way to use your question.

a single bit leaves you with very little room, though. with one bit, i’d ask about the decidability of a small class of problems.

s.

October 11, 2010 3:52 pm

I would ask: would you like to have a cup of coffee?

10. October 11, 2010 4:08 pm

When we should quit for looking solution of an hard mathematical problem?

11. October 11, 2010 4:29 pm

I guess one can make an information theory question of this. If we are interested in n yes/no events with joint entropy H, then how much can we reduce this entropy with one yes-no question?

• October 11, 2010 4:39 pm

I would ask: “Does there exist a feasible strategy by which this planet, by the end of the 21st century, could support 10^7 mathematicians in security, prosperity, liberty, and peace … along with the rest of the planet?”

If the answer is Yes … then we are motivated to get busy … to figure out what that strategy might be. The point being, that any strategy that we humans are smart enough to implement, is likely to be a strategy that we are smart enough to figure out in the first place. And so we receive considerable value from one bit of information.

If the answer is No … then we can simply continue pretty much along present lines … as Dick says, “Oh well” … and at least we are no worse off than at present … except (of course) that we *realize* that we are no worse off than at present. And so in this case too we receive considerable value from one bit of information.

October 11, 2010 4:31 pm

If the results to the questions are independent (not necessarily identically distributed) it seems XOR would be the right function. Reformulate the questions such that 0 is the most likely answer.
Choose large subsets (randomly ? uniform of some size) of the questions and ask is the XOR of this subset=1. The intuition would be from the fact that XOR forms a good lossless source code and it will work if we have entropy rate number of questions.

This should work for dependent variables as well though it may not be the best thing if we have a fixed number of questions (say 3).

October 11, 2010 4:31 pm

In this article there exists a pun so bad it caused its author not to noun a verb.

14. October 11, 2010 5:25 pm

I don’t believe you picked that name just because of Star Trek. It’s too similar to the name of the main character of this blog’s summer episodes 🙂

October 11, 2010 7:06 pm

Alessandro,

No I really did search for an alien name….

October 12, 2010 7:18 pm

Actually Vina was human. She was saved by the Talosians after her ship crashed on Talos IV. True, she did appear to Captain Pike as a green Orion slave girl in one of their illusions, but she was human in the others, and appeared human when they were visibly in their cage.

• October 13, 2010 10:20 am

Vina or Veena is a common girl’s name in India.

15. October 11, 2010 6:19 pm

“Vina, if the market will end up more than 20% one year from now, please answer yes. If the market will end down more than 20% one year from now, please answer no. Otherwise please remain silent.”

Yes -> Buy tons of out of the money call options.
No -> Buy tons of out of the money put options.
No answer -> Sell tons of out of the money puts and calls.

Can be rephrased if silence is not allowed, and the trading strategy can be tweaked too (e.g. use futures, sell the opposite side, etc.)

Then do it with huge size, make enormous money, and found a research institution to answer all sorts of questions.

More generally, ask a question about the future and leverage that one bit of info into trillions of dollars through savvy trading.

16. October 11, 2010 6:46 pm

I agree with K: it’s also worth thinking about an ‘upscale’ interaction with the alien, in which we can present any mathematical statement and learn its truth value, *along with* a proof. (If there’s no proof of less than 1000 page length, let’s say we’re out of luck.)

Let’s say we have statements S_1, … S_k we want to have decided with a single question to the alien. Asking about the AND of the S_i is of course risky since we could just learn a disproof of one of them. Murali’s suggestion to use the XOR is tempting. But it raises the following type of question:

-suppose we get a proof that the truth-value of [P != NP] XOR [Goldbach] is 0. Can we necessarily use this proof to extract proofs/disproofs of the constituents?

It seems like we ought to, since they’re “totally unrelated”. But what do we know, really?
Maybe the two conjectures are equivalent and that’s all we’ll end up learning.

In the setting of finitary interactive proofs, this kind of thing can happen: if one-way functions exist, and S_1, S_2 are PSPACE-decidable statements, then a prover can give an efficient (interactive, probabilistic) proof of the value of S_1 XOR S_2, without revealing anything else about the constituents’ truth-values to a polytime-bounded verifier. (See the complexity zoo entry on CZK.)

October 11, 2010 6:59 pm

Assume you ask : “Vina , will this Turing Machine come to a halt for this given word?”

Given any answer, she knows/thinks an algorithm for the halting problem, therefore the Church-Turing thesis is false. Therefore, Vina’s existence, with the given properties of always answering and truthfullness, disproves the thesis. So by asking 0 questions, you’ve already got a strong result.

The one question to ask would be very tricky… but I doubt that I would ask something about science. I believe my question would be more of an existential nature.

October 11, 2010 10:31 pm

Harry, you’re wrong in assuming its behavior is algorithmic. Moreover, lots of particular instances of the halting problem can be answered by any of us, and yet the Church-Turing thesis may be true.

I think a good question is “What is the best form of government for today human beings?”.

18. October 12, 2010 1:29 am

Two questions come to mind:
(1) Is RSA secure against chosen ciphertext attacks from a polynomial-time bounded adversary?
(2) Is the first number of tomorrow’s winning lottery number odd?

Of course, I’m inclined to be skeptical of someone who claims to have all knowledge. So I like (2) because, if Vina is right, I’ve doubled my chance to win. If she’s wrong, there’s a 50% chance that I’ll learn I was a fool to trust her.

Depending on how far technology has advanced, it may also be useful to try our luck at this one:
(3) May I run your brain through this machine?

• October 12, 2010 12:21 pm

Vina: (3)No.

October 12, 2010 2:28 am

1) Randomness does not help. Consider the simple experiment: Throw *yourself* a die to decide which question to ask, then ask. Obviously, the expected information gain is a convex combination of the information gains for each possible outcome of your die throw, so you can’t be better than choosing the (“deterministic”) question with highest information gain in the first place.
Now compare this to the experiment where you let the alien throw a die. Clearly, you cannot obtain more information than when throwing the die yourself this way. #

2) I think that you can get as close to 1 bit of entropy gain as you can get to equally partitioning the “possible universes” (combinations of answers to your problems) into 50%:50% probability. If I’m not mistaken this follows directly from the entropy definition for such a partition (you obtain exactly the entropy -p1 log p1 – p2 log p2, where p1 + p2 = 1 is the probability partition).

3) How about asking “What would be your answer to the question that has highest expected information gain given these our beliefs: …?” That’s a little cheating, but it gives you time to figure out the best question later.

This question puts you in the same situation as the mice in The Hitchhiker’s Guide to the Galaxy: Deep Thought computes them “the answer to life, universe and all the rest”: 42. But they can’t use the answer yet, because the actual question they posed is still unknown, and so they build Earth to “compute” the question for them.

That said, maybe we should ask the alien the first bit of that question instead. 😉

October 12, 2010 3:23 pm

Good argument for why letting Vina introduce randomness into the answer reduces the information gain. But I would argue that extracting a sub-optimal amount of information (eg. just clearing up our 10% uncertainty in P≠NP) is more helpful culturally than extracting the maximum information about some function of all answers we are interested in.

A bird in the hand is worth a linear combination of half a dozen birds in the bush.

• October 13, 2010 9:48 am

Would randomness in the question help any? If we ask Vina to state, and answer one important question that she knows at random, given that she knows so much more than we do, isn’t there some reasonable probability that the question itself will reveal a significant amount of information, as well as the answer?

Paul.

October 14, 2010 6:03 am

Yes definitely. It would probably good idea to use a different measure than entropy. This has yet to be defined.

Challenge: formulate “A bird in the hand is worth a linear combination of half a dozen birds in the bush.” as an entropy-like measure =)

October 14, 2010 5:33 pm

Carsten–

Given a series of statements S1…Sn which we believe to be correct with probability P1…Pn. If Vina is a simple oracle that just answers yes/no to a deterministic question, then we want to choose some boolean function of f(S1…Sn) such that we believe the probability of f(S1…Sn) is 50%. This will maximize the entropy gain, as you argued.

However, even though this is optimal, I think it would be better for society to just ask Vina if S1 is correct. This will be lower entropy gain, but would be more helpful in terms of advancing our knowledge of mathematics. Knowing that N≠NP is more helpful than knowing that either N=NP or the Riemann hypothesis is false.

20. October 12, 2010 2:48 am

As you say, just being told that P!=NP doesn’t convey all that much information. And the trouble with the “What is the first bit of the shortest proof?” question is that it gives very little hint of what the proof might be like. But a variant such as, “Does there exist a proof using GCT that humans could reasonably be expected to find that shows that P!=NP?” would yield genuinely useful information, since it would tell us either that a certain avenue is very much worth exploring or that we should look elsewhere for a proof. (There’s the drawback that if the answer is no it might be because P=NP, but this question is designed for people who think that is very unlikely.)

October 12, 2010 2:54 am

Vina is all-knowing. Such a being’s very existence is an awesome thing!
The question I would ask is:
How can I become all-knowing like you?
a) That’s impossible.
b) Here are the steps. All easy to accomplish.
c) Here are the steps:
Step 1: Prove or disprove P=NP.
Step 2: Prove or disprove Reimann Hypothesis.
.. and so on.

a – This would be a great disappointment (for me).

b – Everyone would want this. After becoming all-knowing one can solve everything that is to be solved.

c – Atleast we know that becoming all-knowing is not impossible.

22. October 12, 2010 5:18 am

Hmmm … I still think the largest single-bit informatic value is associated to the question posed above: “Does there exist a feasible strategy by which this planet, by the end of the 21st century, could support 10^7 mathematicians in security, prosperity, liberty, and peace … along with the rest of the planet?”

But that question, asked plainly … is somehow too sobering to be much fun.

A larger quantity of fun-per-bit is to be had, via the following practical instantiation of Newcomb’s Paradox.

I would simply hold up my closed hand, and ask “Vinay, am I about to open my hand?”

A precondition to my asking this question is as follows: I make up my mind beforehand to do the opposite of what Vinay says … unless she first provides me with a short, clear resolution of the P≠NP challenge … along with the answers to any and all other questions that I might desire to know.

By this strategy, in order to speak even one bit of truth, Vinay can be coerced to exert herself to please and delight us by freely sharing *all* her knowledge; thus we see that honest omniscient beings are wholly vulnerable to what we may call Newcombian coercion.

No doubt, these two dismal options for Vinay—facing up to too-sobering planetary realities versus enduring the humiliation of Newcombian coercion—explain why honest omniscient being seldom visit our planet. It’s because beings like Vinay foresee that we humans are going to “cheat” … by coercing her to answer hard questions … that she knows we should be answering for ourselves.

• October 13, 2010 4:39 am

Note that she could always say ‘No’ and then kill you, resolving the issue.

• October 13, 2010 9:53 am

If Vina is all-knowing (or at least hugely advanced), does this increase or decrease the probability that she will deem us as a threat of some kind? Are we more likely to be scared of less advanced creatures — like sharks — then more advanced ones like dogs?

October 12, 2010 6:45 am

Interesting question.
I think there is not a limit of how much information we can get with an one bit answer .
To get more information we can increase the size of the question .
The best we can do given a limit of N bits in question is to ask the next bit to Vina of a bit string with a Kolmogorov complexity of N such that the bit string plus the new bit is ha a Kolmogorov complexity of N+1

24. October 12, 2010 8:57 am

“What is the one true theorem, not currently known by humans, which, if known, would most greatly revolutionize mathematics?”

• October 20, 2010 3:52 pm

Definitely something like this. Maybe I want to change true theorem (which is kind of redundant :D) to ‘method’ or ‘strategy’

25. October 12, 2010 1:11 pm

Interesting question, and some really interesting comments.

Is Vina really “all-knowing”? Certainly just by her presence she is clearly technically advanced, but how could she know some piece of trivia that happened last week before her arrival? If she told us she was all-knowing, then she’s not truthful either is she?

If she did just give us one bit, say whether or not the Riemann Hypnosis is true, it doesn’t really help us much because we can’t just use “Vina said so” as the basis of the proof. We need to know the why and how, as much as the final statement.

If we were looking for the smallest thing from her that would make the greatest improvement in our knowledge than it would have to be a clarification of something we think we know, but currently are wrong about. Of course, that would mean that it is something that everybody thinks is true, but only some crazy person really suspects differently. For example, say a few thousand years back, most people agreed that the world is flat, since to them that’s exactly what it appears to be (mostly). The right question then might have been “what is the shape of our world?”

Our best current question would have to be general, and involve some aspect of the way we are currently modeling the universe around us, which we can speculate about, but are unable to answer without a significant leap in our technological capabilities. I like Xamuel’s comment, which would work nicely, but I’d also be interested in generalized questions about things like infinity or singularities. Unfortunately, I’m not crazy enough to know what the question should really be 🙂

Paul.

• October 17, 2010 3:23 am

Even if we were to ask if the Riemann Hypothesis were true (or indeed, if any open conjecture is true or false), we should be formulating the question as, “What is a counterexample disproving the Riemann Hypothesis?” If there is a counterexample, we have it and we’re done. We don’t really care how we find counterexamples so long as we know they’re there; in many cases, we brute-force our way to those (within known constraints) anyway.

If there is no counterexample, we have the green light to keep searching for a proof. As you rightly point out, the knowledge that the hypothesis is true is not good enough for our standards of proof, and it certainly isn’t good enough for our pride as a theorem-proving species. Knowing the truth of a conjecture doesn’t satisfy our understanding in the least, but knowing its falsity would tell us if we are wasting our time.

P-versus-NP is a little different, though. The analogous question for P and NP would be something like, “What is a polynomial-time algorithm for 3-SAT?” Having an answer would tell us P=NP, but that still leaves it up to us to find all the other efficient algorithms for everything in NP-complete (never mind determining the status of everything in NP-hard). The only thing that would change is that we would be directed towards doing that rather than searching for a proof of P≠NP, although having something like an algorithm for 3-SAT to further transform or reduce would obviously be a massive leap forward.

Even this would be unsatisfying, I think. Not to knock the efforts of mathematicians who tighten the bounds of potential counterexamples, but we take a certain pleasure in developing the conceptual tools for finding efficient algorithms that simply isn’t there when we do a brute-force search for counterexamples to, say, Goldbach’s conjecture. “Looking up the answer” isn’t quite the same.

All of this speaks for the depth and generality of the P-versus-NP problem more than anything else.

• October 17, 2010 4:38 am

A quick correction – by “massive leap forward” I of course meant to say that being handed a single efficient algorithm would make everything else click into place pretty darn quickly, NP-completeness being what it is. But it would still be unsatisfying.

• October 17, 2010 11:37 am

The shortest polynomial-time algorithm for 3-SAT could be larger than we could store at this moment on all computers in the world.

• October 17, 2010 1:57 pm

@Nicholas, if we were sure one way or another we could ask something like “what are the properties of algorithms that makes P != NP?” It might take us a while to turn that into a proof but at least we’d be able to utilize the answer. If we only had 1 bit, then possibly “what is a property that makes P != NP?” would lead us in the right direction. This also hedges a bit because if she answers that there are 0 of them, we can make a valid conclusion.

@Frans, unbounded (potentially) because the algorithm itself is huge, or because it needs lots of data?

Paul.

26. October 12, 2010 2:02 pm

Oops—this may seem like another “No, Puff the Magic Drag’n wasn’t a ref to pot” or “Lucy in the Sky with Diamonds was a kid’s doodle not LSD”, but: while editing this post I did not connect “Vina” to Vinay Deolalikar at all.

It sounded like a good “Vegan” name, and may have been lodged in our brains from Vina being a principal character in the classic Star Trek episode “The Menagerie”, though actually she is human not alien.

Also incidentally, the post is all Dick’s—it did not originate in my funny answer to when I thought P != NP would be solved in Bill Gasarch’s poll in the late 1990’s.

• October 12, 2010 2:28 pm

As with Ken, my own misspelling of “Vina” as Vinay” too was wholly unconscious … In particular, I have immense respect for Vinay Deolalikar’s well-considered present strategy of “be patient and keep quiet while peer review does its work”.

October 12, 2010 2:31 pm

If I could ask an ordinary question, I would ask which is the running time of the best possible exact deterministic algorithm for Sharp-Monotone-2SAT? If I could only ask a one-bit question, I would ask is that running time exponential?

October 12, 2010 7:38 pm

As Carsten Milkau points out, having Vina randomly select a question to answer doesn’t help, and in fact provides less information than you would have if you specified the question explicitly (since you don’t know which question was answered). In the original example, “yes” implies that A or B is true, which is strictly weaker than knowing that in fact A is true, or that in fact B is true. Similarly, “no” implies that either A or B is false, which again is strictly weaker than knowing that in fact A is false, or that in fact B is false. In both cases, the stronger answers imply the weaker ones.

More generally, any algorithm in which Vina is required to choose a random number should give equivalent results if she were instead handed a table of random numbers to use. Peeking at those numbers (either before or after hearing her answers) provides additional information. And specifying the numbers yourself without resorting to any kind of random number generator gives you strictly more control over what information you receive.

October 13, 2010 9:09 am

Tom,

There is a point here. What if YOU have no access to random coins. They does it help to have Vina handle such questions?

October 13, 2010 4:27 pm

As long as you have some way of selecting a single question from your set of questions, then I would argue that giving her a single question is always better. Even if she were to not only give you the answer to a randomly chosen question from your list, but also told you which question she had chosen, I still think it’s no better than simply asking her a single question, assuming that whatever method you use to select the question is at least as likely to pick a “good” question as a random coin toss is.

October 14, 2010 6:13 am

It does not matter whether you have random coins available. This holds because the experiment where you throw the random coins yourself is purely fictional, to show that it is never better than a (suitable) deterministic choice and never worse than a random choice (of same distribution) by Vina. Thus, for every question involving coin tosses by Vina, there is a question without coin tosses that achieves at least the same expected information gain, no matter whether you could really toss the coins yourself.

October 14, 2010 6:31 am

Also note that, in case you use randomness in a more creative way than just picking a question, you could still derandomize the answer by incorporating your quality measure into your question. More formally:

Instead of asking “Tell me f(x) given this f and taking x from this distribution” you can ask “Tell me f(x) such that g(x) is maximal given this f and this g and taking x from this domain”.

g(x) could be the entropy gain of knowing f(x) or whatever quality measure you like. Note we are allowed to specify f, g and the domain/distribution of x in natural language.

• October 14, 2010 8:45 am

Carsten Milkau:
g(x) could be the entropy gain of knowing f(x) or whatever quality measure you like.

So you think anybody’s “quality measure” can be turned into a function?
The variety of comments in this thread does not seem to support this freakish idea.

October 14, 2010 9:28 am

Since Vina is all-knowing, in fact, it already knows your notion of quality, so you could express g(x) as “1 for the x I would consider most useful, having access to your full knowledge, and 0 otherwise.” So yes, I am pretty sure you could express anybody’s quality measure as a g(x), and in fact I just did 😛

• October 14, 2010 9:47 am

Ha! Ha!
To me this highlight the major flaw in the question:
What does all-knowing means?
For any specific program does Vina can tell if it is terminating or not?
Is she a living oracle for the halting problem?
Is she immune to the Newcomb Paradox?

October 12, 2010 8:41 pm

When asking mathematical questions we assume that our fundamentals are sound. What if the alien declines to answer, stating that the question is ill-formed?

October 12, 2010 10:53 pm

Maybe Vina knows everything, but does it really matter if she can’t convince anyone that her
If i would ask “does P equal NP” and get a yes-or-no-answer, either theres no reason to believe her or prooving her answer is correct wouldn’t be to different from prooving P = NP in the first place.
There’s no point in asking her anything.

October 12, 2010 11:23 pm

I take back my previous post. As a thought experiment, if you take Vina’s credibility for granted just to see what would happen, there is of course a different motivation for asking the question.

I still have a question about:
“Are there reasons, advantages, to ask questions that involve Vina flipping coins?”

Isnt it always better to flip the coin yourself and then ask the question? Where exactly
would be the obvious advantage of Vina flipping the coin?

31. October 13, 2010 12:18 am

Come on, Dick aside, we all know that NP does not equal P. So if we only are allowed one bit of response, we certainly shouldn’t ask about that. We should ask if factoring is in BPP.

32. October 13, 2010 12:00 pm

I think my best question is “Vina, will you be my research guide?” and the best possible answer is “Yes”.

October 13, 2010 1:00 pm

The price of the priceless little book called “The P=NP Question and Gödels Lost Letter” went up to \$99 😦

October 13, 2010 1:50 pm

By coincidence i was abduced yesterday by some aliens and casually one of them was called Vina. The others told me that she was knowledge all-powerful and that i could only ask one question, several bits answer allowed.

I asked: if i was knowledge all-powerful what would you ask me ? If i was knowledge all powerful what would you ask me ? she answered …errr…she asked.

October 13, 2010 4:48 pm

You could try to back her into a corner with an underhanded question like: Will your answer to this question be “no” if you refuse to answer 10 more questions, your original statement to the contrary notwithstanding? No matter how she answers, the implication is that she is not refusing to answer 10 more questions. But presumably questions of this sort would not be allowed.

November 2, 2010 6:42 pm

Actually, the question “Will you give the ‘no’ answer to this question?” is good enough. Although we already know the true answer, Vina will be hard-pressed to give it to us. So we can blackmail her into giving away all her omniscience. =P

36. October 13, 2010 8:35 pm

It’s by finding this stuff out ourselves (and finding our //how// to find it out) that we grow as a species.

October 14, 2010 12:21 pm

Even as an atheist, i think it’s remarkable that nobody would ask the obvious question.
“Does THE book really exist?” 🙂

38. October 17, 2010 7:15 am

I would want to know whether an alien supercommunity had deduced a solution to a related Darwinian question. About the origin of dreams;is it all really indigestion and superficial tiredness catching up on us when usually answers are easy awake to most things or they are not. The alien would never be as friendly to ask any such things I ponder….being a perfect B-hyphen in lieu of-