Minsky's neural automata

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 $\vert Q\vert\vert\Sigma\vert$ units which detect a particular combination of state and input symbol and $\vert\Gamma\vert$ 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