Computational power of neural networks: a characterization in terms of Kolmogorov complexity

DOI10.1109/18.605580zbMath0878.68103OpenAlexW2099977515WikidataQ56058051 ScholiaQ56058051MaRDI QIDQ4345611

Ricard Gavaldà, José L. Balcázar, Hava T. Siegelmann

Publication date: 23 July 1997

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/18.605580

zbMATH Keywords

neural networksTuring machinesKolmogorov complexity

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Neural networks for/in biological studies, artificial life and related topics (92B20) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results, Subrecursive neural networks, Three analog neurons are Turing universal, The expressive power of analog recurrent neural networks on infinite input streams, Quasi-periodic \(\beta\)-expansions and cut languages, Computational capabilities of analog and evolving neural networks over infinite input streams, Oracles and Advice as Measurements, Automata complete computation with Hodgkin-Huxley neural networks composed of synfire rings, Analog neuron hierarchy, Kobayashi compressibility, Cut Languages in Rational Bases, A Hierarchy for $$ BPP //\log \!\star $$ B P P / / log ⋆ Based on Counting Calls to an Oracle, Continuous-Time Symmetric Hopfield Nets Are Computationally Universal, The structure of logarithmic advice complexity classes, Stochastic analog networks and computational complexity, Continuous-Time Symmetric Hopfield Nets Are Computationally Universal