3 ms·
Are you familiar with the idea that to prove a loop correct only takes two things: A/ proving (o->o), that it makes progress with each iteration, and B/ provi
by 082349872349872 4y ago
Are you familiar with the idea that to prove a loop correct only takes two things:
A/ proving (o->o), that it makes progress with each iteration, and
B/ proving (->o), that it terminates?
If so, he's speaking a bunch of different alien languages, showing how the same basic pattern (prove something for an infinite number of things by looking at their structure and proving something for the finite number of ways each of those things can be put together) works in each of the alien languages.
Or at least that's what I got from the few of those languages which I speak — all the rest are, as they say, greek to me.
- deleted 4y ago[deleted]
- mrmuagi 4y agoInduction proofs are indeed useful, the strongest argument for learning these sort of formal tricks, is you can convince another human that your algorithm correct with pure math. It's one thing to say, look, my program's test suite (that I wrote) passes, or it passes a few criteria, it is another thing entirely to prove without a shadow of a doubt the algorithm is logically sound and correct. Induction proofs are useful with loops, but there are a lot of tricks useful for programmers.