Turing Machines, Finite Automata and Neural Nets

Abstract

This paper ¹ compares the notions of Turing machine, finite automaton and neural net. A new notation is introduced to replace net diagrams. “Equivalence” theorems are proved for nets with receptors, and finite automata; and for nets with receptors and effectors, and Turing machines. These theorems are discussed in relation to papers of Copi, Elgot and Wright; Rabin and Scott; and McCulloch and Pitts. It is shown that sets of positive integers “accepted” by finite automata are recursive; and a strengthened form of a theorem of Kleene is proved.