The basic result of the incompleteness proofs is pretty simple. The proofs are complicated because the idea was literally unthinkable until programming was invented. The heroic efforts of Gödel, Skolem, Post, and Church to create a mathematics in which doing mathematics
the terrible effect of Krohn-Rhodes
One of the most interesting theorems in computer science is the Krohn-Rhodes theorem that shows a strong link between basic computer science and group theory. Crudely, the KR theorem extends Jordan-Holder \( (H_1 \triangleleft H_2 … \triangleleft H_n=G)\) to state
Gödel’s Lost Letter
Gödel’s perspective in this letter is a refutation of the simplistic take on Turing’s proof seen so often in the computer science literature. In particular: After all, one would simply have to choose the natural number n so large that
Are threads evil? (updated)
This paper by Prof. Edward Lee explains something of why “threads” are such a painful abstraction. As Prof. Lee notes, threads intrinsically create unspecified program operation (which he calls non-determinism) and resource conflicts which we then attempt to “prune” via
Dijkstra versus Perlis (updated)
Dijkstra wrote: He [Perlis] published a very obnoxious paper arguing against a mathematical approach to programming cite The paper by De Millo, Lipton and Perlis starts as follows: Many people have argued that computer programming should strive to become more like mathematics.
more on missed wakeup
Here are some conventions [Update: typos fix, Friday] We are concerned with state machines and sequences of events. The prefixes of a sequence include the empty sequence “null” and the sequence itself. Relative state: If “w” is the sequence of
Data structures and algebra
[Edited 9/10] There’s an easy connection between data structures and basic abstract algebra that may or may not mean anything, but keeps getting rediscovered. I’ve never seen it clearly explained (anyone with a reference or who notices an error in