See also: Von Neumann’s critique of automata theory and logic in computer science
Von Neumann on the empirical roots of mathematics
Rabin-Scott Finite Automata and Their Decision Problems
One of the most important Computer Science papers introduced finite state machine language recognizers, the equivalence between non-deterministic and deterministic finite automata (in terms of what languages they recognize) , the Myhill congruences, etc.
Mathematics errors in computer science
A trivial theorem, more of a tautology, on networking and Turing’s deep theorem on decidability are both widely cited, widely misunderstood and widely misapplied in computer science. It is often claimed that Fischer, Lynch, Patterson (FLP) “theorem” on networks shows
Lecture notes on Paxos
PAXOS – (c) Victor Yodaiken, 2022 These are the lecture notes, or see the paper. 1. Really clever distributed consensus algorithm by Leslie Lamport A. Infamously hard to understand – but not complicated B. Livelocks – can get stuck without
Sorting algorithms as recursive functions
This paper is an experiment in presenting programming algorithms as recursive functions, without pseudo-code or genuine code. The algorithms presented are the standard basic sorting algorithms with some computational complexity analysis. The style is that of ordinary working mathematics although
Paxos demystified
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 enormously insightful – no surprise. Von Neumann essentially predicts the emergence of the field of analysis of algorithms and algorithmic complexity. Not only does he point out the
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