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 (16)

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

This page was built for publication: Computational power of neural networks: a characterization in terms of Kolmogorov complexity