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