Computer Science and State Machines

Leslie Lamport

Concurrency, Compositionality, and Correctness (Essays in Honor of Willem-Paul de Roever). Dennis Dams, Ulrich Hannemann, and Martin Steffen editors. Lecture Notes in Computer Science, number 5930 (2010), 60-65. | , pp. 60-65

This is the six-page version of [165]. I think it is also the first place I have mentioned the Whorfian syndrome in print. It is structured around a lovely simple example in which an important hardware protocol is derived from a trivial specification by substituting an expression for the specification’s variable. This example is supporting evidence for the thesis of [168] that computation should be described with mathematics. (Substitution of an expression for a variable is an elementary operation of mathematics, but is meaningless in a programming language.)