On the Computational Power of Neural Nets

1995/02/01 by Hava T. Siegelmann, H.T. Siegelmann, E.D. Sontag +1 · 701 citations
Computer Science · Mathematics · #Algorithm #Computability, Logic, AI Algorithms #Computer science #Decidability #Discrete mathematics #Evolutionary Algorithms and Applications #Finite-state machine #Function (biology) #Mathematics #Neural Networks and Applications #Programming language #Pushdown automaton #Recursive functions #Theoretical computer science #Time hierarchy theorem #Turing #Turing machine #Universal Turing machine

paper · doi:10.1006/jcss.1995.1013

published in Journal of Computer and System Sciences 50(1), 132-150 (Elsevier BV)

openalex publication_date 1995/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Cited by

• Constructing Turing complete Euler flows in dimension 3
• Continuous Ordinary Differential Equations and Transfinite Computations
• Learning a Prior over Intent via Meta-Inverse Reinforcement Learning
• Rational Recurrences
• Connectionist-Symbolic Machine Intelligence using Cellular Automata based Reservoir-Hyperdimensional Computing
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• Analyzing and Interpreting Neural Networks for NLP: A Report on the First BlackboxNLP Workshop
• Strongly-Typed Recurrent Neural Networks
• Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages
• Encoding-based Memory Modules for Recurrent Neural Networks
• Generative Teaching Networks: Accelerating Neural Architecture Search by Learning to Generate Synthetic Training Data
• State of the Art in Fair ML: From Moral Philosophy and Legislation to\n Fair Classifiers
• Empirical Study on Deep Learning Models for Question Answering
• SPARK: Static Program Analysis Reasoning and Retrieving Knowledge
• Dynamical Systems Implementation of Intrinsic Sentence Meaning
• Multigrid Neural Memory
• Distance and Equivalence between Finite State Machines and Recurrent Neural Networks: Computational results
• Theoretical Limitations of Self-Attention in Neural Sequence Models
• On the Turing Completeness of Modern Neural Network Architectures
• Multilingual Neural Machine Translation for Zero-Resource Languages
• A Fully Trainable Network with RNN-based Pooling
• Hierarchical Conflict Propagation: Sequence Learning in a Recurrent Deep Neural Network
• Winner-Take-All Computation in Spiking Neural Networks
• Neural Turing Machines
• Universality of Gradient Descent Neural Network Training
• Transforming Agency. On the mode of existence of Large Language Models
• What they do when in doubt: a study of inductive biases in seq2seq learners
• Memory and attention in deep learning
• Learning to update Auto-associative Memory in Recurrent Neural Networks for Improving Sequence Memorization
• Survey of reasoning using Neural networks
• A Model for Auto-Programming for General Purposes
• Higher Order Recurrent Neural Networks
• Dataflow Matrix Machines as a Model of Computations with Linear Streams
• Neural Stored-program Memory
• A Distributed Extension of the Turing Machine
• On Computability, Learnability and Extractability of Finite State\n Machines from Recurrent Neural Networks
• Entangled Datasets for Quantum Machine Learning
• AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence
• Formal models of Structure Building in Music, Language and Animal Songs
• Feedforward Sequential Memory Networks: A New Structure to Learn Long-term Dependency
• Learning and Generalization in RNNs
• Reservoir Computing using Cellular Automata
• A Minimal Intervention Definition of Reverse Engineering a Neural Circuit
• Neural Machine Translation: A Review and Survey
• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Dataflow Matrix Machines and V-values: a Bridge between Programs and Neural Nets
• Predicting the Future with Transformational States
• Advances in Natural Language Question Answering: A Review
• Adversarial Resilience Learning - Towards Systemic Vulnerability Analysis for Large and Complex Systems
• Synthesizing Context-free Grammars from Recurrent Neural Networks (Extended Version)
• Learning Context-Aware Representations of Subtrees
• Derivatives of Turing machines in Linear Logic
• Computational power of neural networks: a characterization in terms of Kolmogorov complexity
• A Survey of Continuous-Time Computation Theory
• What Formal Languages Can Transformers Express? A Survey
• Unifying syntactic theory and sentence processing difficulty through a connectionist minimalist parser. [europepmc]
• Letting the brain speak for itself. [europepmc]
• Computation in dynamically bounded asymmetric systems. [europepmc]
• Training Excitatory-Inhibitory Recurrent Neural Networks for Cognitive Tasks: A Simple and Flexible Framework. [europepmc]
• EMG-Based Continuous and Simultaneous Estimation of Arm Kinematics in Able-Bodied Individuals and Stroke Survivors. [europepmc]
• How Organisms Gained Causal Independence and How It Might Be Quantified. [europepmc]
• Symbolic Modeling of Asynchronous Neural Dynamics Reveals Potential Synchronous Roots for the Emergence of Awareness. [europepmc]
• Models that learn how humans learn: The case of decision-making and its disorders. [europepmc]
• Echo State Networks with Self-Normalizing Activations on the Hyper-Sphere. [europepmc]
• Turing complete neural computation based on synaptic plasticity. [europepmc]
• Bootstrapping Knowledge Graphs From Images and Text. [europepmc]
• Difficulties in analysing animal song under formal language theory framework: comparison with metric-based model evaluation. [europepmc]
• Short-Time Wind Speed Forecast Using Artificial Learning-Based Algorithms. [europepmc]
• An IOHMM-Based Framework to Investigate Drift in Effectiveness of IoT-Based Systems. [europepmc]
• An Entropy Metric for Regular Grammar Classification and Learning with Recurrent Neural Networks. [europepmc]
• Robust high-dimensional memory-augmented neural networks. [europepmc]
• Universal Nonlinear Spiking Neural P Systems with Delays and Weights on Synapses. [europepmc]
• Biologically-Inspired Pulse Signal Processing for Intelligence at the Edge. [europepmc]
• Long-Short Term Memory Network-Based Monitoring Data Anomaly Detection of a Long-Span Suspension Bridge. [europepmc]
• Cracking the genetic code with neural networks. [europepmc]
• Using deep neural networks as a guide for modeling human planning. [europepmc]
• When philosophical nuance matters: safeguarding consciousness research from restrictive assumptions. [europepmc]
• Predicting human decision-making across task conditions via individuality transfer. [europepmc]
• Synthesizing Context-free Grammars from Recurrent Neural Networks [europepmc]