Download
The halting problem has nothing to do with computers
“Turing’s work was of course a great contribution to the world of mathematics, but there is a question of exactly how it is related to the world of computing. – Wilkes The undecidability of the halting problem for Turing
Von Neumann’s critique of automata theory and logic in computer science
These remarks from “THE GENERAL AND LOGICAL THEORY OF AUTOMATA” 1947 are, not surprisingly, enormously insightful. Von Neumann essentially predicts the emergence of the field of analysis of algorithms and algorithmic complexity. Not only does he point out the importance
Judea Pearl’s mysterious claim
Pearl: Of course, but you cannot see this noble aspiration in scientific equations. The language of algebra is symmetric: If x tells us about y, then y tells us about x. I’m talking about deterministic relationships. There’s no way to write in mathematics a simple fact—for example,
Trees in informal methods
What’s a tree? First define a sequence or length n> 0 as a total map s: {1,.. n}→ X. Let Nil be the empty sequence. If s is a sequence of length n, and x is an element, then u
Linked lists
What’s a linked list? Let V be a set of values and A be a set of “addresses”. Say a map f is a “linked list element” compatible with values V and addresses A if and only if f(value)∈ V
informal methods applied to networks and timeouts
Distributed computation involves many interesting issues concerning shared data. Here I want to sketch out what networks look like using applied (informal) mathematics so we can look at some algorithms for consensus and data consistency. No formal methods or category
Sorting and groups
I can’t find much reference to this in the literature (see Maus for some hints and an interesting paper) , but surely people have looked at sorting as a problem in group theory? Given a sequence $latex s=[x_1\dots x_n] $
Basic math for basic algorithms
It’s odd that all the descriptions of basic programming operations, such as sorting, rely on pseudo code or complex formal logic. All we are doing is modifying finite sequences so it seems like we should be able to use ordinary
circularity problems in distributed consensus
Distributed consensus involves organizing a collection of independent agents – processes or network sites – to agree on some value or sequence of values. Many distributed consensus methods depend on a leader-follower scheme in which the leader is an agent