4 ms·

isn't it actually one program? Imagine the implementation using an oracle. You being a clever programmer somehow know of a very powerful oracle, lets call the

isn't it actually one program? Imagine the implementation using an oracle. You being a clever programmer somehow know of a very powerful oracle, lets call the oracle Pauli. You're program works as follows: func main(): response = write_pauli_asking_if_p_is_np() //synchronous, waits for response if response is true: print(“P=NP.”) else: print(“P≠NP.”)

omnicognate 2y ago
I don't think that's what he was referring to. Apart from not being "fast", it's not a program in the sense being discussed here, given the article is about computability. It's an oracle turing machine rather than a plain turing machine, and oracle turing machines can trivially side step computability questions by having the oracle evaluate the noncomputable function. (This is of course not relevant to the oracle you suggest as that doesn't evaluate a noncomputable function, but it's relevant to what sort of "program" Aaronson is talking about here.)
5- 2y ago
nit: > if response is true: i've always wondered how people know when to stop (which, i guess, is relevant to the subject matter). e.g. why is your next step not > if (response is true) is true:
- inexcf 2y ago
  I would say it's because this is pseudo code and it is a lot clearer that way. Depending on language >if response: could mean "response" is true,1,not empty, X....
derbOac 2y ago
To me there's no other way to interpret it, really, except as one function. The if-then part of it is part of the function definition. The example is genuinely confusing to me because of the igtheism problem: the idea that the question of whether God exists is a poorly posed one, because God is undefinable. It's like dividing by zero or a type error or something. This was Bertrand Russell's perspective, for example. Maybe the intent of the example is "here is a function whose inputs are unknown" but for me it was more like "here is a function whose outputs depend on an undefinable input." The second example didn't seem much better for the same reason. Knowing that the output is prime regardless of the input — a logical conclusion from the "meta evaluation" of the function — doesn't seem to me to be the same as asking whether the function is computable. To me it's like having the function depend on a contingency sort of like "if the color blue tastes like cheese, then..." It doesn't make sense. If the example was meant to incorporate an unknown state (as opposed to an undefinable one), it would have been better off with a random unseen event or something, like a person flipping a coin in a different room. Or a particle decay in a box, but then that leads to quantum issues maybe which leads to the same sort of problem possibly.
- pdonis 2y ago
  > The if-then part of it is part of the function definition. No, it isn't. The if-then part of the question is about which of two trivial functions the label "f" refers to. It has nothing to do with the functions themselves or their computability. That, from what I can gather, is supposed to be the point of the question, but I don't think the question gets that point across very well.

omnicognate 2y ago

I don't think that's what he was referring to. Apart from not being "fast", it's not a program in the sense being discussed here, given the article is about computability. It's an oracle turing machine rather than a plain turing machine, and oracle turing machines can trivially side step computability questions by having the oracle evaluate the noncomputable function. (This is of course not relevant to the oracle you suggest as that doesn't evaluate a noncomputable function, but it's relevant to what sort of "program" Aaronson is talking about here.)

5- 2y ago

nit: > if response is true: i've always wondered how people know when to stop (which, i guess, is relevant to the subject matter). e.g. why is your next step not > if (response is true) is true:

inexcf 2y ago
I would say it's because this is pseudo code and it is a lot clearer that way. Depending on language >if response: could mean "response" is true,1,not empty, X....

derbOac 2y ago

To me there's no other way to interpret it, really, except as one function. The if-then part of it is part of the function definition. The example is genuinely confusing to me because of the igtheism problem: the idea that the question of whether God exists is a poorly posed one, because God is undefinable. It's like dividing by zero or a type error or something. This was Bertrand Russell's perspective, for example. Maybe the intent of the example is "here is a function whose inputs are unknown" but for me it was more like "here is a function whose outputs depend on an undefinable input." The second example didn't seem much better for the same reason. Knowing that the output is prime regardless of the input — a logical conclusion from the "meta evaluation" of the function — doesn't seem to me to be the same as asking whether the function is computable. To me it's like having the function depend on a contingency sort of like "if the color blue tastes like cheese, then..." It doesn't make sense. If the example was meant to incorporate an unknown state (as opposed to an undefinable one), it would have been better off with a random unseen event or something, like a person flipping a coin in a different room. Or a particle decay in a box, but then that leads to quantum issues maybe which leads to the same sort of problem possibly.

pdonis 2y ago
> The if-then part of it is part of the function definition. No, it isn't. The if-then part of the question is about which of two trivial functions the label "f" refers to. It has nothing to do with the functions themselves or their computability. That, from what I can gather, is supposed to be the point of the question, but I don't think the question gets that point across very well.