On the computational power of neural nets

By Hava T. Siegelmann, Eduardo Sontag. 1992

This paper deals with finite networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a “sigmoidal” scalar nonlinearity to a linear combination of the previous states of all units. We prove that one may simulate all Turing Machines by rational nets. In particular, one can do this in linear time, and there is a net made up of about 1,000 processors which computes a universal partial-recursive function. Products (high order nets) are not required, contrary to what had been stated in the literature. Furthermore, we assert a similar theorem about non-deterministic Turing Machines. Consequences for undecidability and complexity issues about nets are discussed too.

Subfields: Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Model Architectures

Citations in the corpus

Long Short-Term Memory-Networks for Machine Reading (2016, background): “In practice, however, it has proven challenging to model long input sequences for at least two reasons.”
Neural Turing Machines (2014, background): “Moreover, it is known that RNNs are Turing-Complete (Siegelmann and Sontag, 1995), and therefore have the capacity to simulate arbitrary procedures, if properly wired.”
On the difficulty of training recurrent neural networks (2012, background): “awing similarities with Dynamical Systems One can consider yet another perspective, namely that of dynamical systems. Recurrent networks are universal approximators of dynamical systems (see for e.g. Siegelmann and Sontag (1995)) and as such it is sometimes useful to analyze them using dynamical sys”
The Best of Both Worlds: Combining Recent Advances in Neural Machine Translation (2018, background): “From a theoretical point of view, RNNs belong to the most expressive members of the neural network family (Siegelmann and Sontag, 1995)4.”
Generalization in anti-causal learning (2018, background): “Recent works analyzing how to adaptively control the computation time of RNNs include (Graves, 2016; Figurnov et al., 2017).”
Siamese Recurrent Architectures for Learning Sentence Similarity (2016, neutral): “…networks for sequence data ( x 1 , . . . , x T ) , where at each t ∈ { 1 , . . . , T } , updates to a hidden-state vector h t are performed via While Siegelmann and Sontag (1995) have shown that the basic RNN is Turing-complete, optimization of the weight-matrices is difﬁcult because its…”
On the Turing Completeness of Modern Neural Network Architectures (2019, methodology): “As mentioned earlier, the ﬁrst work showing the Turing completeness of ﬁnite neural networks with linear connections was carried out by Siegelmann & Sontag (1992; 1995).”
A survey of computational complexity results in systems and control (2000, background): “A result announced in Siegelmann and Sontag (1991) and completed in Siegelmann and Sontag (1995), shows that saturated linear systems are capable of simulating Turing machines .”
Artificial neural networks trained through deep reinforcement learning discover control strategies for active flow control (2018, background): “…solve any problem since they are universal approximators: a large enough feed-forward neural network using a non linear activation function can fit arbitrarily well any function (Hornik et al., 1989), and the Recurrent Neural Network paradigm is even Turing complete (Siegelmann & Sontag, 1995).”
Trends and Applications in Constructive Approximation Evolutionary Optimization of Neural Systems: the Use of Strategy Adaptation (unknown): “Abstract models of neural networks (NNs) exist, which can—in principle—simulate all Turing machines and exhibit universal approximation properties (e.g., [40] [42] [44]).”
Understanding the exploding gradient problem (2012, background): “Recurrent networks are universal approximators of dynamical systems (see for e.g. Siegelmann and Sontag (1995) ) and as such it is sometimes useful to analyze them using dynamical systems tools which allow for better abstractions that we can use for reasoning about the behaviour of the model.”
On Evaluating the Generalization of LSTM Models in Formal Languages (2018, background): “Siegelmann and Sontag (1992) and Siegelmann (1995) showed that ﬁrst-order RNNs (with rational state weights and inﬁnite numeric precision) can simulate a push-down automaton with two-stacks, thereby demonstrating that RNNs are Turing-complete.”
Neural Machine Translation: A Review (2019, background): “RNNs are theoretically Turing-complete [416] and thus potentially very powerful models of computation.”
Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples (2017, background): “While all these functions are theoretically equally expressive (the Elman RNN can theoretically represent any turing-computable function [29]), the gated architectures were shown empirically to be much easier to train, and capable of learning complex concept classes.”
Multi-Temporal Land Cover Classification with Sequential Recurrent Encoders (2018, methodology): “In theory, the iterative update of h t enables RNNs to simulate arbitrary procedures [27], since these networks are Turing complete [28].”
Empirical Study on Deep Learning Models for QA (2015, background): “NTMs are essentially RNNs, which in turn are Turing-complete [10] and capable of encoding any computer program in theory, yet not always practical.”