[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.