He’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).
But "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.
Proving 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.
Nit, decision problems are one type of computable problems, but you have other types like function problems, optimization problems, etc.
NP, by definition involves decision problems, but many NP-Hard problems are optimization problems.
More specifically NP is the set of decision problems solvable by a NTM in poly time with the following conditions:
1) If the answer is "yes," at least one computation path accepts.
2) If the answer is "no," all computation paths reject
Equivalently is is the set of decision problems verifiable by a TM in poly time.
Modern programming tends to only care about #1, and structured programming paradigm helps with that.
People not moving past NP in complexity theory is the real problem here. I also blame using the 'trys all answers at once' NTM intuition vs the max lucky guesser which makes it less silly.
But didactic half truths do really hurt. Entscheidungsproblem is better for teaching people in my experience.
Part 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.
> But "we don't know which of the two it is" handwaves away that "answering P vs NP" means precisely coming up with the proof!
Of course it's a not a proof of "P=NP", but no one is asking for it.
> 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.
Yes. This function is still computable though. The question of computability doesn't depend on humans being able to evaluate this function on a given day in history.
The whole point is simply that the notion of computability is not related to coming up with proofs or to any mechanical process for arriving at a result based on a set of axioms. "Computable" and "Provable in ZFC (or whatever)" are just two different things and pertain to different mathematical objects. Functions are computable (or not). Theorems are provable (or not).
Correct, the author did not describe a program that computes whether P = NP. He merely proved that such a program exists, by describing two programs, and showing that one of them must be the one that computes whether P = NP (we just don't know which one, but we at least know that it exists).
I think the intuition people want to apply here is that ‘is P=NP’ feels like an instance of a class of questions - ‘is P=x’, and if that is computable, then it implies we can attack P=NP by coming up with a way to compute it and feeding in NP.
But I think the issue there is the assumption that it even makes sense to define a function over ‘classes of questions’.
