zbMATH — the first resource for mathematics

The computational limits to the cognitive power of the neuroidal tabula rasa. (English) Zbl 1084.68112
Summary: The Neuroidal Tabula Rasa (NTR) as a hypothetical device that is capable of performing tasks related to cognitive processes in the brain was introduced by L. G. Valiant in 1994. Neuroidal nets represent a computational model of the NTR. Their basic computational element is a kind of a programmable neuron called neuroid. Essentially, it is a combination of a standard threshold element with a mechanism that allows modification of the neuroid’s computational behaviour. This is done by changing its state and the settings of its weights and of threshold in the course of computation. The computational power of an NTR crucially depends both on the functional properties of the underlying update mechanism that allows changing of neuroidal parameters and on the universe of allowable weights. We will define instances of neuroids for which the computational power of the respective finite-size NTR ranges from that of finite automata, through Turing machines, up to that of a certain restricted type of BSS machines that possess super-Turing computational power. The latter two results are surprising since similar results were known to hold only for certain kinds of analog neural networks.

68T05 Learning and adaptive systems in artificial intelligence
68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI
[1] Blum M., Complexity and Real Computation (1997)
[2] Hopcroft J. E., Formal Languages and their Relation to Automata (1969) · Zbl 0196.01701
[3] Indyk, P. Optimal Simulation of Automata by Neural Nets. Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science STACS’95. pp.337–348. · Zbl 1379.68223
[4] DOI: 10.1006/jcss.1995.1013 · Zbl 0826.68104 · doi:10.1006/jcss.1995.1013
[5] Šma J., Journal of the ACM 45 pp 155– (1998) · Zbl 0902.68170 · doi:10.1145/273865.273914
[6] Valiant, L. G. Functionality in neural nets. Proceedings of the 7th National Conference on Artificial Intelligence, AAAI. pp.629–634. San Mateo, CA: Morgan Kaufmann.
[7] Valiant L. G., Circuits of the Mind (1994) · Zbl 0839.68078
[8] Valiant L. G., Proceedings of the 38th IEEE Symp. on Fond. of Comp. Sci. pp 2– (1995)
[9] Watanabe, O. and Yokomori, T., eds. Algorithmic Learning Theory. Proceedings of 10th International Conference, ALT’99, Lecture Notes in Artificial Intelligence. December, Tokyo, Japan. pp.63–76. · Zbl 0929.00070
[10] Wiedermann, J. Toward algorithmic explanation of mind evolution and functioning. Proceedings of Mathematical Foundation of Computer Science 1998 – Lecture Notes in Computer Science. Vol. 1450, pp.152–166. Berlin: Springer.
[11] Wiedermann J., ACM Computing Surveys 31 (1999) · doi:10.1145/333580.333595
[12] Wiedermann, J. and van Leeuwen, J. Emergence of super-Turing computing power in artificial living systems. Proceedings of Advances in Artificial Life 2001 (ECAL 2001), Lecture Notes in Artificial Intelligence. Vol. 2159, pp.55–65. Berlin: Springer-Verlag. · Zbl 1011.68503
[13] Wiedermann J., AI Communications (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.