### The difference between unspecified, undefined, and non-deterministic

There is too much confusion in the "formal methods" computer science literature between these three different terms. Let me start with what this means for a state machine and then move on to engineering objects such as threads. Suppose we have a map α: X → Y  where X is the set…

### Keynes apology

The composition of this book has been for the author a long struggle of escape, and so must the reading of it be for most readers if the author's assault upon them is to be successful,—a struggle of escape from habitual modes of thought and expression. The ideas which are…

### Process algebra versus state machines part 1

Robin Milner's influential book Communication and Concurrency involves a take on state machines that has always puzzled me. "Now in standard automata theory, an automaton is interpreted as a language," Milner writes "i.e. as a set of strings over the alphabet." That's not at all correct, but let's accept the…

### More on Fischer, Lynch, Patterson and the parrot theorem.

I'm thinking about distributed consensus algorithms, timestamping, and databases and if you read that literature you will see many references to the Fischer, Lynch, Paterson "theorem". Here is the problem statement The problem is for all the data manager processes that have participated in the processing of a particular transaction…

### Theories of abstract automata – Arbib

We have said that automata theory deals with the realization of partial functions F: X* —» Y* by some finitely specifiable substrate. Before we specify in more detail the forms (of which the Turing machine is one) of substrate which have figured most prominently in automata theory, it is useful…

### Kirkhart’s conjecture

Is that there is some insight into the nature of primes that comes from considering the classes of numbers that share the same set of prime factors. For example 2x3x5 = 30, 4x3x5 = 60, 2x9x5 = 90, 2x3x25 = 150, 4x3x25=300 ... all of these have the same set…

### RTLinux early paper from 20 years ago

An early RTLinux paper with Michael Barabanov. real_time_1996 Only 20 years later, the idea is now not too scary.   Real-Time Linux Michael Barabanov Victor Yodaiken March 3, 1996 1 Introduction If you wanted to control a camera or a robot or a scientific instrument from a PC, it would…

### ultrafinitism

I have seen some ultrafinitists go so far as to challenge the existence of 2100 as a natural number, in the sense of there being a series of “points” of that length. There is the obvious “draw the line” objection, asking where in 21, 22, 23, … , 2100 do…

### RISC-V and Bloat

Went to UT today to listen to David Patterson speak about the open RISC  instruction set architecture and processors he and his colleagues are developing.  As a software developer, hearing about free hardware makes me giddy with joy, perhaps with a bit too much of a "let's see how you…