# Meaning (and proof) of “RNN can approximate any algorithm”

Recently I read that a recurrent neural network can approximate any algorithm.

So my question is: what does this exactly mean and can you give me a reference where this is proved?

• Check the works of Halbert White. I think it was him who proved a neural network is a universal approximator. (Not sure about recurrent neural networks, though.) – Richard Hardy Jun 28 '16 at 6:28

Background

We first have to go over some concepts from the theory of computation. An algorithm is a procedure for calculating a function. Given the input, the algorithm must produce the correct output in a finite number of steps and then terminate. To say that a function is computable means that there exists an algorithm for calculating it. Among the infinite set of all functions, most are not computable. Turing machines are a mathematical model that formalizes the notion of computation. Other equivalent models exist, but Turing machines are the standard 'reference model'. According to the Church-Turing thesis, any algorithm can be implemented by a Turing machine, and all computable functions can be computed thusly. Any particular instance of a Turing machine only computes a particular function. But, there exist a special class of Turing machines called universal Turing machines that can simulate any other Turing machine for any input. They do this by taking a description of the machine to be simulated (and its input) as part of their own input. Any particular instance of a Universal Turing machine can therefore compute any computable function (i.e. can implement any algorithm). Any system that shares this ability is called Turing complete. One way to prove that a system is Turing complete is to show that it can simulate a universal Turing machine. Many systems have been shown to be Turing complete (e.g. most programming languages, certain cellular automata, and quantum mechanics).

Recurrent neural networks

The following paper shows that, for any computable function, there exists a finite recurrent neural network (RNN) that can compute it. Furthermore, there exist finite RNNs that are Turing complete, and can therefore implement any algorithm.

Siegelmann and Sontag (1992). On the computational power of neural nets

They use networks containing a finite number of recurrently connected units, which receive external inputs at each time point. The state of each unit is given by a weighted sum of its inputs (plus a bias), run through a nonlinear activation function. The activation function is a saturated linear function, which is a piecewise linear approximation of a sigmoid. The weights and biases are fixed, so no learning occurs.

The network performs a mapping from a binary input sequence to a binary output sequence. There are two external inputs to the network, which are fed to all units: a 'data line' and a 'validation line'. The data line contains the input sequence of zeros and ones, then zero after the input sequence is finished. The validation line lets the network know when the input sequence is happening. It contains one for the duration of the input sequence, then zero after it has finished. One unit is considered to be the 'output unit'. It outputs zeros for some arbitrary delay, then the output sequence of zeros and ones, then zero after the output sequence has finished. Another unit is considered to be the 'validation unit', which let's us know when the output sequence is happening. It outputs one while the output sequence is happening, and zero otherwise.

Although these RNNs map binary input sequences to binary output sequences, we might be interested in functions defined on various other mathematical objects (other types of numbers, vectors, images, graphs, etc.). But, for any computable function, these other types of objects can be encoded as binary sequences (e.g. see here for a description of encoding other objects using natural numbers, which can in turn be represented in binary).

Result

They show that, for every computable function, there exists a finite RNN (of the form described above) that can compute it. They do this by showing that it's possible to use a RNN to explicitly simulate a pushdown automaton with two stacks. This is another model that's computationally equivalent to a Turing machine. Any computable function can be computed by a Turing machine. Any Turing machine can be simulated by a pushdown automaton with two stacks. Any pushdown automaton with two stacks can be simulated by a RNN. Therefore, any computable function can be computed by a RNN. Furthermore, because some Turing machines are universal, the RNNs that simulate them are Turing complete, and can therefore implement any algorithm. In particular, they show that there exist Turing complete RNNs with 1058 or fewer units.

Other consequences

An interesting consequence of the simulation results is that certain questions about the behavior of RNNs are undecidable. This means that there exists no algorithm that can answer them for arbitrary RNNs (although they may be answerable in the case of particular RNNs). For example, the question of whether a given unit ever takes the value 0 is undecidable; if one could answer this question in general, it would be possible to solve the halting problem for Turing machines, which is undecidable.

Computational power

In the above paper, all network parameters and states are rational numbers. This is important because it constrains the power of the RNNs, and makes the resulting networks more realistic. The reason is that the rationals are computable numbers, which means that there exists an algorithm for calculating them to arbitrary precision. Most real numbers are uncomputable, and therefore inaccessible--even the most powerful Turing machine can't represent them, and many people doubt that they could even be represented in the physical world. When we deal with 'real numbers' on digital computers, we're accessing an even smaller subset (e.g. 64 bit floating point numbers). Representing arbitrary real numbers would require infinite information.

The paper says that giving the network access to real numbers would boost the computational power even further, beyond Turing machines. Siegelmann wrote a number of other papers exploring this 'super-Turing' capability. However, it's important to note that these are mathematical models, and the results don't mean that such a machine could actually exist in the physical world. There are good reasons to think that it couldn't, although it's an open question.

• hey, I find this super interesting, I was wondering if you have any reference to learn more about this theory of computation and its relation to machine learning algorithms or quantum computing. Thanks! – user110320 Mar 7 at 23:00

I think this is what you're looking for. This guy proved that a multilayer, or even a single layer feedforward network could approximate any function, provided that the net has enough hidden units.

Hornik, K. (1991). Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2), 251-257.

• this is not what I meant. I already read the proof for that. I edited my question. – user3726947 Jun 28 '16 at 22:12