Timeline for What do we mean by "Proving an algorithm"?
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 12, 2012 at 22:56 | comment | added | Andreas Blass | I agree with this answer in the case of more-or-less traditional algorithms, computing some function, which is almost surely what the OP meant. Nevertheless, it might be worthwhile to mention that other notions of proof are appropriate for other sorts of algorithms. For example, if the algorithm uses randomization, you might want to prove reasonable lower bounds for the probability of termination and/or correctness. If the "algorithm" is an operating system, you might want to prove that it doesn't terminate. | |
| Feb 12, 2012 at 17:23 | history | answered | Guillaume Brunerie | CC BY-SA 3.0 |