Turing computability with neural nets

By Hava T. Siegelmann, Eduardo Sontag. 1991

How researchers see this paper

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

Citations in the corpus

On the Binding Problem in Artificial Neural Networks (2020, background): “Indeed, while an RNN can in principle perform any kind of computation using only its hidden state as memory (Siegelmann and Sontag, 1991), its dual purpose for representing structure and information processing makes it difficult to learn programs that generalize systematically (Lake and Baroni, 2018”
Learning Precise Timing with LSTM Recurrent Networks (2003, background): “In fact, while HMMs and traditional discrete symbolic grammar learning devices are limited to discrete state spaces, RNNs are in principle suited for all sequence learning tasks because they have Turing capabilities (Siegelmann and Sontag, 1991).”
Learning Stochastic Recurrent Networks (2014, background): “One typical application is to let an RNN model a probability distribution over sequences, i.e. p ( x 1: T ) .”
On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, background): “Unlike feedforward NNs (FNNs; [95, 23]) and Support Vector Machines (SVMs; [287, 253]), RNNs can in principle interact with a dynamic partially observable environment in arbitrary, computable ways, creating and processing memories of sequences of input patterns [258].”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “It was shown in Siegelmann and Sontag [49] that all Turing machines can be simulated by recurrent networks built of neurons with non-linear activations.”
Self-Delimiting Neural Networks (2012, neutral): “Compare [69] for a more complex argument.”
Deep Convolutional and LSTM Recurrent Neural Networks for Multimodal Wearable Activity Recognition (2016, background): “These types of networks have Turing capabilities [18] and, thus, are in principle suited for learning sequences.”
Recurrent Inference Machines for Solving Inverse Problems (2017, methodology): “Recurrent neural networks (RNN) can implement any algorithm because they are Turing complete [1, 2].”
Analysis and Design of Echo State Networks (2007, background): “RNNs are perhaps the most biologically plausible of the artificial neural network (ANN) models (Anderson, Silverstein, Ritz, & Jones, 1977; Hopfield, 1984; Elman, 1990), but are not well understood theoretically (Siegelmann & Sontag, 1991; Siegelmann, 1993; Kremer, 1995).”
Training Recurrent Networks by Evolino (2007, background): “In particular, they can approximate any dynam ic l system with arbitrary precision [44].”
LSTM recurrent networks learn simple context-free and context-sensitive languages (2001, background): “ECURRENT neural networks (RNNs) are remarkably general sequence processing devices [ 22 ].”
For neural networks, function determines form (1992, background): “In discrete time, systems of the type (7) have been recently shown to be at least as powerful as any possible digital computational device (see Siegelmann & Sontag, 1991, 1992) when all weights are rational numbers and a general model of analog computers when the weights are allowed to be real…”
Recurrent policy gradients (2010, background): “Not only can RNNs represent memory, they can, in theory, be used to model any dynamic system [21].”
Computation in Recurrent Neural Networks: From Counters to Iterated Function Systems (1998, unknown): “In [13] it has been shown that there are no ultimate limitations imposed by the use of neural networks as computing devices and that we do not even need higher order neural networks to have enough computational power.”
Computational capabilities of recurrent NARX neural networks (1997, background): “fixed, finite number of saturated linear activation functions are universal computation devices [7], [8].”