This chapter discusses the implementation of finite-state machines (formulated as Mealy machines) using McCulloch and Pitts (1943)'s neurons ; it starts by building very simple automata such as gates, switches, impulse counters, and simple arithmetic circuits, and finally proves a theorem which is crucial to the field that connects artificial neural networks and the formal theories of language and computation. In Minsky's own words, ``every finite-state machine is equivalent to, and can be simulated by, some neural net''. The theorem constructs a recurrent neural net in which there are units which detect a particular combination of state and input symbol and units which compute outputs. The neural net is shown to exhibit the same behavior as the corresponding Mealy machine.

It is worth mentioning that the net itself is a neural Moore
machine, architecturally very similar to
Elman (1990)'s nets and that Minsky's
construction has inspired other work such as
Kremer (1995)'s or
Alquézar and Sanfeliu (1995)'s
.^{3.2}