Notes

Chapter 6: Starting from Randomness

Section 7: The Notion of Attractors


Finite automata

The networks discussed in the main text can be viewed as finite automata (also known as finite state machines). Each node in the network corresponds to a state in the automaton, and each arc represents a transition that occurs when a particular value is given as input. NetCAStep above in general produces a non-deterministic finite automaton (NDFA) for which a particular sequence of values does not determine a unique path through the network. MinNet creates an equivalent DFA, then minimizes this. The Myhill-Nerode theorem ensures that a unique minimal DFA can always be found (though to do so is in general a PSPACE-complete problem).

The total number of distinct minimal finite automata with k=2 possible labels for each arc grows with the number of nodes as follows: 3, 7, 78, 1388, ... (The simple result (n+1)^(n k) based on the number of ways to connect up n nodes is a significant overestimate because of equivalence between automata with different patterns of connections.)


From Stephen Wolfram: A New Kind of Science [citation]