4 ms·
> "If you ask an amateur whether their program is correct, they are likely to be offended." But if you ask a computer scientist, they will know the right answe
by Swizec 16y ago
> "If you ask an amateur whether their program is correct, they are likely to be offended."
But if you ask a computer scientist, they will know the right answer is "I have no way of knowing, but it works on some known cases".
And that's a very important part of looking for people who "Write large correct programs" - the fact that we simply can't know when a program is correct.
- akkartik 16y agoNobody knows unknown unknowns, but good programmers will be able to enumerate the kinds of errors they're guarding against.
- joe_the_user 16y agoIt's easy to escalate all of the discussion here. Poor programmer expect to be correct. Better programmers guard against a variety of error types The best programmers are constantly thinking up new ways things could good wrong, not satisfied with just a set list And I'm sure we could add more.
- jberryman 16y ago> the fact that we simply can't know when a program is correct What do you mean? Correctness of a program means it works according to the specification. Programs can be proven correct.
- Swizec 16y agoThey cannot. It is simply impossible to prove that a given algorithm behaves well for all inputs (that is to say for all memory states). You can show that it works as desired for a subset of the problem and infer from there that it will most likely work for other inputs as well. But you cannot prove it perfectly. You can sometimes strictly prove an algorithm is correct, but that still leaves your implementation, your compiler, your physical machine and a myriad other things in question.
- FaceKicker 16y ago> It is simply impossible to prove that a given algorithm behaves well for all inputs (that is to say for all memory states). No, it's not. People write proofs of algorithms all the time (see the Cormen Rivest book for several examples). This belief stems from a misinterpretation of Rice's theorem ( http://en.wikipedia.org/wiki/Rice%27s_theorem http://en.wikipedia.org/wiki/Rice%27s_theorem ), which says that you can not, in general, create a Turing machine that gives a yes or no answer to any particular property of an input algorithm. That does not, however, mean that you cannot prove particular properties of algorithms for particular algorithms.
- jberryman 16y agoI'm sorry. That's simply not true. For instance a program that takes one bit of input and always outputs the 1 bit. This can be trivially proven correct.