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.
RTLinux retrospective
Kuth’s Merge Sort in C
Taken from Knuth Algorithm S mergesort P162-163 Vol 3 Second edition 1998 The major change is that the scratch buffer is not required to be adjacent and there are some changes because C array indexing starts with 0. This is
State machines for large scale computer software and systems
Sequential functions can be used to define and compose large scale state machines that represent computer software and hardware. The mathematical basis is introduced and there are motivating examples, including a proof of the safety of the Paxos algorithm. https://www.yodaiken.com/wp-content/uploads/2023/12/fac_sm_published_acm.pdf
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
Process algebra and automata theory
Milner’s Communication and Concurrency contrasts a notion of “bisimulation” with what he characterizes as the view in standard automata theory. Standard automata theory, however, has a much more interesting and well defined notion of both equivalence and concurrency than what
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