4 ms·
In this case, I don't see why the proof is considered to be the output of the program, but rather the entire program itself. If you can verify the soundness of
by baddox 13y ago
In this case, I don't see why the proof is considered to be the output of the program, but rather the entire program itself. If you can verify the soundness of the software and hardware involved (I certainly can't, but I presume the verification has been done), why should a human need to actually read the output?
- Pxtl 13y agoand now we're into questions about homoiconicity. I think I see why Lisp was so popular in AI research.
- ColinWright 13y agoBecause the output of the program is effectively a long list of cases of things that have been considered[0], and why they do or don't "work" in some sense. The output is independent of the program and, in principle, can be checked. In some ways it's like printing the search tree of chess to show that white has a forced win. It doesn't matter if the program is "correct" - you can check the output separately. [0] EDIT: actually it's the certificate from a SAT solver
- samatman 13y agoI believe "Someone" is wondering whether it's possible, and if so helpful, to work out the common factors in those search trees and give them names, much as a certain chess search tree could efficiently be called "Stonewall White" if it represented all boards reachable from that class of opening.
- baddox 13y agoI get that, but all these articles are worried about the fact that no human could possibly read and verify the output of the program. So why even bother? Why not just verify the software and hardware that generates the output?
- dllthomas 13y agoA CS prof I had held the position (in grading his tests - perhaps not generally) that "a proof is anything that convinces me you could write a proof". The program, along with an output saying "true", would seem to suffice under that metric.
- ColinWright 13y agoIt's a certificate output by a SAT solver. More, you can't guarantee that there wasn't a bit flip caused by a cosmic ray. Verifying the hardware and software isn't enough. And yes, the whole question is to ask to what extent we can trust this. Personally, it's just as likely that a human proof would have a subtle and hard-to-find error, missed by all the reviewers. All the popular articles are claiming this humungous output is a proof. It's not a proof, it's a certificate from a SAT solver. There's a difference, and most comments people are making based on the popular accounts are misguided.
- baddox 13y ago> More, you can't guarantee that there wasn't a bit flip caused by a cosmic ray. Hmm. Are bit flips from cosmic rays more likely than a human making a mistake verifying a proof, or even a large number of humans making the same mistake?
- ColinWright 13y agoIf one human makes the mistake, it's probably because it's a mistake that humans trained in this field are likely to make. Mistakes are not independent in this sense. Also, the number of humans capable of an in-depth analysis of the result is small, and they've mostly all got the same training, so if there's a subtle mistake, it's one to which they are all susceptible.
- scott_s 13y agoIf the certificate from the SAT solver does not count as a proof, you can't blame the popular accounts. That's the language the paper authors use: The negative witness, that is, the DRUP unsatisfiability certificate, is probably one of longest proofs of a non-trivial mathematical result ever produced. Its gigantic size is comparable, for example, with the size of the whole Wikipedia, so one may have doubts about to which degree this can be accepted as a proof of a mathematical statement. From http://arxiv.org/pdf/1402.2184v2.pdf http://arxiv.org/pdf/1402.2184v2.pdf