2
$\begingroup$

If you could ask one computational yes/no question, what would it be?

To be precise, you get to specify a Turing machine (in a convenient language) and an oracle will tell you whether or not it halts. You only get one query (let's say filesize < 1TB); it's answered immediately; and you know for a fact that the answer you get is correct.

For example, you could ask "Does there exist a proof that $\mathsf{NP}\ne\mathsf{P}$?" by specifying a Turing machine that enumerates all proofs and halts when it finds such a proof. But is that the best question to ask?

$\endgroup$
5
  • $\begingroup$ Most scientists will probably want to know about P and NP, but what is the motivation for your question? Is there a big philosophic golden nugget you want to lay on us? :-) $\endgroup$ – William Hird May 10 '15 at 7:34
  • $\begingroup$ Beside the "P vs NP" question (my first choice) I would be tempted to give the event a "zen-twist": generate a 1TB random TM and ask the oracle if it halts :-) :-) :-) $\endgroup$ – Marzio De Biasi May 10 '15 at 14:55
  • $\begingroup$ I think I'd ask if zero squared is really 1 $\endgroup$ – user34089 May 13 '15 at 6:25
  • $\begingroup$ Better zen twist: "what would this oracle answer if I asked it to tell me the opposite answer to the current question?" $\endgroup$ – cody May 13 '15 at 17:51
  • $\begingroup$ This is a bad fit for this site, but I think it would be a fun question for a blog post or /r/compsci. In particular, I could think of several reasons why you would not want to know the answer to P vs NP if you get only the answer and not an intelligible proof. For some nice reflections on this, I recommend: Rav, Y., (1999) Why do we prove theorems? Philosophia Mathematica, 7(3): pg. 5-42. $\endgroup$ – Artem Kaznatcheev May 13 '15 at 20:56

Browse other questions tagged or ask your own question.