Neural computability. II
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 631-637 vol.1
- https://doi.org/10.1109/ijcnn.1989.118643
Abstract
The authors present a general framework within which the computability of solutions to problems by various types of automata networks (neural networks and cellular automata included) can be compared and their complexity analyzed. Problems solvable by global dynamics of neural networks, cellular automata, and, in general, automata networks are studied as self-maps of the Cantor set. The theory derived from this approach generalizes classical computability theory; it allows a precise definition of equivalent models and thus a meaningful comparison of the computational power of these models. The authors show that neural networks are at least as powerful as cellular automata and that the converse is true for finite networks. Evidence indicates that the full classes are probably identical. The proofs of these results rely on the existence of a universal neural network, of interest in its own right.Keywords
This publication has 14 references indexed in Scilit:
- Memory capacity in neural network models: Rigorous lower boundsPublished by Elsevier ,2003
- Neural network modelling by means of networks of finite automataPublished by Springer Nature ,1991
- Embedding graphs in Cayley graphsGraphs and Combinatorics, 1987
- Computing with Neural Circuits: A ModelScience, 1986
- Dynamical Behaviour of Neural NetworksSIAM Journal on Algebraic Discrete Methods, 1985
- Simulating physics with cellular automataPhysica D: Nonlinear Phenomena, 1984
- Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences, 1982
- Tessellations with local transformationsJournal of Computer and System Sciences, 1972
- Endomorphisms and automorphisms of the shift dynamical systemTheory of Computing Systems, 1969
- A logical calculus of the ideas immanent in nervous activityBulletin of Mathematical Biology, 1943