[skissane]

> Because if you literally enumerate over all Turing machines, including trivial ones like those that ignores the input and just acceps/halt no matter what, then it doesn't help you solve the problem at all...

I think there is a step which was not explicitly stated in the GP comment. When a given Turing machine accepts, we check whether its output is a valid proof of the answer to our problem. Per definition of NP, we can check that proof in polynomial time. If the check passes, we accept. If the check fails, we ignore that accept and move on.

So we are executing all possible Turing machines in parallel, not just the ones that accept the problem. And when any of them accept, we have to check whether the accept should be ignored or not, because most of the Turing machines are doing something completely unrelated to our problem.

[hnfong]

Yeah after I commented I read the wikipedia link in a sibling comment -- which basically says what you said. Having programs/Turing Machines generate 'proofs' and checking them in P does seems legit.