Preview Mode Links will not work in preview mode

QED 19: Dependency Tracking

Oct 24, 2016

The number of degrees of freedom in a system is equal to its number of unknowns minus its number of equations. That is also equal to the number of independent variables in the system. Dependent variables do not contribute degrees of freedom. However, by taking advantage of determinism, we can compute at run time the set...

Q.E.D. 18: Paxos

Sep 19, 2016

Leslie Lamport wrote a paper describing the Paxos algorithm in plain English. This is an algorithm that guarantees that a distributed system reaches consensus on the value of an attribute. Lamport claims that the algorithm can be derived from the problem statement, which would imply that it is the only algorithm that...

QED 17: Pythagoras

Aug 27, 2016

The Pythagoreans were a cult of Greek mathematicians that believed that all things were composed of large enough integers. Their leader, Pythagoras, is best known for the proof that the square of the hypotenuse of a right triangle is equal to the sum of the squares of the two sides. Unfortunately, this theorem leads...

QED 16: Elements

Aug 15, 2016

Euclid's Elements takes a disciplined, formal approach to proving assertions based only on simple axiomatic statements. While most of these axioms are elegant, one of them is more complex and wordy. It seems as if it should be provable from the others. Several mathematicians have tried, but eventually they found...

QED 15: The Y Combinator

Jul 16, 2016

The Lambda Calculus uses simple replacement to compute expressions. However, it does not define a way to replace a parameter of a function with the function itself. That would seem to make it impossible to write recursive functions. However, with a clever bit of self-application, we can define a function that makes any...