3 ms·
> Indeed, a fast program that correctly answers the P vs. NP question trivially exists: > If P=NP, then the program prints “P=NP.” > If P≠NP, then the program
by omnicognate 2y ago
> Indeed, a fast program that correctly answers the P vs. NP question trivially exists:
> If P=NP, then the program prints “P=NP.”
> If P≠NP, then the program prints “P≠NP.”
That's not a program, it's two programs. Likewise for the theological "function" at the start. If it were to determine whether God exists it would need inputs on which to base that determination. Instead, two functions are presented along with a theological rule to choose between the two. The properties of the functions have nothing to do with the theological question.
I get that that's the point of the article, and that the quoted homework question correctly refers to two functions. I just felt that it wasn't particularly clearly spelled out and that the article seemed to blur the distinction between the functions and the choices between functions, which would probably further confuse those suffering from the misconception he describes (while heaping scorn upon them).
Edit: And this seems to really muddy the waters:
> The deeper lesson Sipser was trying to impart is that the concept of computability applies to functions or infinite sequences, not to individual yes-or-no questions or individual integers.
Regardless of Sipser's motivations the question doesn't say anything about the difference between individual values and functions/sequences. What it reveals is the difference between a well defined mathematical function and a choice one might make or imagine between various such functions (the criteria for which may or may not be well defined).
I could replace the question about God with one about whether some other function (which we haven't yet determined the computability of) is computable and it would still be the case that "the function we have defined is computable". (Scare quotes because that's actually a category error and the correct observation is that "both functions we have defined are computable". Hmm, well given the computability of the third function is well defined, though unknown, I suppose in this case we actually have defined a single unknown function, but the point about the difference between the choice and the functions stands.)
- soganess 2y agoisn'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 agoI 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 agonit: > 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 agoI 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 agoTo 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.
- foldr 2y agoHe’s saying that because those two programs exist, there exists a program that correctly answers the P vs NP question. We don’t know which of the two it is. But equally, 50 years ago we would not have known whether to choose the program “Fermat’s last theorem is false” or “Fermat’s last theorem is true”. Still, the second program has always existed and has always printed the correct answer (at least if you sub in the theorem in pre-Fermat times).
- debugnik 2y agoBut "we don't know which of the two it is" handwaves away that "answering P vs NP" means precisely coming up with the proof! Those constant functions aren't proofs, the proof is in coming up with a series of computable steps to reduce a model of P=NP into that constant function. That is, the proof is the computation itself, not just the constant value. What the author did describe is a function that we can only evaluate when we already have an answer for P = NP, not a function that computes it.
- michaelmior 2y agoPart of the point is that computability is different from knowing how to write a program that actually computes the desired value. We can say a program exists to print whether P=NP (whether it is computable) without knowing how to come up with a concrete implementation of that program.
- jltsiren 2y agoProving P vs. NP and answering the question correctly are two different problems. Computability is defined in terms of functions that map the input to yes/no. A function is computable if there exists a representation that computes it correctly for any input and eventually terminates. Every yes/no question where the answer does not depend on the input is by definition computable. The corresponding function is either the one that maps every input to "yes" or the one that maps every input to "no". We may not know which one, but that's irrelevant. In some sense, computability is similar to probability. Your intuition is wrong, and following it only leads to further confusion. But if you unlearn it and rebuild it from basic principles, things become much clearer.
- akira2501 2y ago> I could replace the question about God with one about whether some other function Saint Anselm's Ontological Theory of Computation. "First.. imagine the most perfect function that could possibly exist.."
- H8crilA 2y agoIt is one program. If P=NP then the body of the program consists of "print(P=NP)". And otherwise it consists of "print(P!=NP)". [1] Similarly for every hash function there exists a program that outputs a hash collision in well under a second. Just hardcore any collision and print it to the screen. [2] [1] If you want to be pedantic then there's a third option that prints some more complicated statement about the relationship between standard axioms and P?=NP. [2] Please don't ruin my short argument by pointing out that someone can create a hash function with output size in the petabytes range :)
- rdlw 2y ago> That's not a program, it's two programs Yes, and one of them is "a fast program that correctly answers the P vs. NP question". We don't know which.