4 ms·

Would you mind explaining how learning proofs has helped you? I'm currently studying computer science on my own, so I would appreciate any tips.

nayuki 6y ago
The ability to read and write proofs lets me confirm truth independently, without needing to blindly trust someone's claims. As a quick analogy, if you know how to do arithmetic by hand, you can check whether an electronic calculator is faulty. In my opinion, here are the most important mathematical topics in computer science which are related to proofs: Basic algebra, inequalities, functions, set theory, Boolean algebra, predicates, quantification (for-all & there-exists), weak&strong&structural induction, formal definition of big-O notation, preconditions & postconditions, loop invariants, termination, recursion, regular languages, Turing machines, computability. Example: If you don't know the true definition of big-O, you can still identify common patterns by counting the number of nested loops. But there are non-standard cases (e.g. Euclid's GCD algorithm) and contrived pathological cases where you must appeal to the formal definition in order to prove anything. Example: Somebody hands you a red-black tree data structure plus algorithms, in either pseudocode or real code. How can you justify that their work is correct and won't corrupt data? You need to do proof by cases, structural induction, and big-O analysis. Example: You design a new algorithm for analyzing graphs which doesn't resemble anything in published literature. You can't just reuse other people's analyses, so you have to write your own. Without understanding how to do proofs, you're doomed to either cobbling together high-level libraries or creating things with subtle flaws. You'd be unable to synthesize new knowledge or fill in small gaps, due to not grasping the underlying theory.
- Alekhine 6y ago
  Thank you for writing this. To be blunt I don't understand about half of the terms you used, but I eventually will. Have you ever read Euclid's Elements? I recently took one of the few classes left in the country that uses Euclid, and I've been thinking about what a computer science student could glean from it in 2020.

nayuki 6y ago

The ability to read and write proofs lets me confirm truth independently, without needing to blindly trust someone's claims. As a quick analogy, if you know how to do arithmetic by hand, you can check whether an electronic calculator is faulty. In my opinion, here are the most important mathematical topics in computer science which are related to proofs: Basic algebra, inequalities, functions, set theory, Boolean algebra, predicates, quantification (for-all & there-exists), weak&strong&structural induction, formal definition of big-O notation, preconditions & postconditions, loop invariants, termination, recursion, regular languages, Turing machines, computability. Example: If you don't know the true definition of big-O, you can still identify common patterns by counting the number of nested loops. But there are non-standard cases (e.g. Euclid's GCD algorithm) and contrived pathological cases where you must appeal to the formal definition in order to prove anything. Example: Somebody hands you a red-black tree data structure plus algorithms, in either pseudocode or real code. How can you justify that their work is correct and won't corrupt data? You need to do proof by cases, structural induction, and big-O analysis. Example: You design a new algorithm for analyzing graphs which doesn't resemble anything in published literature. You can't just reuse other people's analyses, so you have to write your own. Without understanding how to do proofs, you're doomed to either cobbling together high-level libraries or creating things with subtle flaws. You'd be unable to synthesize new knowledge or fill in small gaps, due to not grasping the underlying theory.

Alekhine 6y ago
Thank you for writing this. To be blunt I don't understand about half of the terms you used, but I eventually will. Have you ever read Euclid's Elements? I recently took one of the few classes left in the country that uses Euclid, and I've been thinking about what a computer science student could glean from it in 2020.