4 ms·
Overheard at the watercooler: The only way a CS guy knows how to prove an algorithm works/does not work is to find counterexamples.
by itissid 3y ago
Overheard at the watercooler: The only way a CS guy knows how to prove an algorithm works/does not work is to find counterexamples.
- aoki 3y agoMy real analysis instructor drily pointed out “You really like proof by contradiction huh” and my defense was that my main life skill is spotting why plausible-seeming things don’t work correctly
- User23 3y agoWatercooler guy has never heard of Mathematical Engineering or Edsger Dijkstra. If he had then he'd know that proof by construction is the method par excellence for showing an algorithm is correct.
- JohnKemeny 3y agoSeems hard to prove that an algorithm works by finding counterexamples.
- panda-giddiness 3y agoJust express it as an n-state Turing machine and see if it halts within BB(n) steps. /s
- AnimalMuppet 3y agoAnd, if n is large enough, then I can retire today.
- contravariant 3y agoI think most bugs are the result of someone's attempt to do just that. As is test-driven development I suppose. Then again proving code works isn't everything either. There's a reason Knuth once stated "Beware of bugs in the above code; I have only proved it correct, not tried it." Type checking is a nice intermediate, though not all languages allow all properties you care about to be encoded in types.
- morkalork 3y agoI would've picked proof by induction for CS peeps!