4 ms·

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

• Swizec 15y ago
  They 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 15y 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 15y ago
    I'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.