1
$\begingroup$

I know it has been shown that RNNs are Turing complete. So for any Turing machine, there exists a configuration of a RNN that is equivalent to it.

But I'm wondering, is all those configuration reachable through learning/training? i.e. For any Turing machine, does there exist a data set and a training process, which will finish in finite time and generate an equivalent RNN?

$\endgroup$
1
$\begingroup$

The RNN construction of the paper is independent of training, because the weights are fixed and no learning occurs. The proof is based on how the encoding of the input output mechanism should be translated into an RNN so that it behaves the same as a Turing machine given the same input. They construct an RNN equivalent to a two-stack push-down automata, which can simulate any Turing machine. They also end up with a Turing complete universal processor net with 1058 units.

Training process is an approximation for a function, thus accuracy is always a parameter to decide on the computation time. Theoretically speaking, for a network with finite number of processors, and with weights and states represented with rational numbers (computable numbers), which is also a translation of a computable function (i.e. not a real random number generator for each sample), it should converge. Thus, the answer is yes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.