Turing Machines, Finite Automata and Neural Nets

ABSTRACT

This paper1 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.

REFERENCES

• 1: BUHKS, A. W., AND WRIGHT, J. B Theory of logical nets. Proc. IRE 41, No 10 (1953), 1357-1365.
• 2: Irving M. Copi , Calvin C. Elgot , Jesse B. Wright, Realization of Events by Logical Nets, Journal of the ACM (JACM), v.5 n.2, p.181-196, April 1958 [doi>10.1145/320924.320931]
• 3: DAVlS, MARTIN Computability and Unsolvab,12ty. McGraw-Hill, New York, 1958.
• 4: KLEENE, S.C. Representation of events m nerve nets and finite automata. In Automata gtudies, ed by C. E. Shannon and J. McCarthy, Princeton University Press, 1956, pp. 341.
• 5: McCULIOCH, W. S., AND PITTS, W. A logical calculus of the ideas immanent in nervous activity. Bull. Math. Bwphys 5 (1943), 115-133.
• 6: RABIN, M. O., AND SCOTT, D. Finite automata and thcir decision problems IBM J., Res. Dev. 8 (1959), 114-125.
• 7: TURING, A. M. On computable numbers, with an application to bile Entscheidungsproblem. Proc. London Math. Soc. (2), 42 (1936-7), 230-265; with a correction, Ibid. 43 (1947), 544-546.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Theory, Verification