7
$\begingroup$

The Universal Approximation Theorem says that under certain conditions on your activation function, you can approximate any bounded continuous function with a feedforward neural network.

I believe this result can be extended to LSTMs, since with certain choices, the LSTM can be simplified into a feedforward network.

Is there a stronger result for LSTMs?

$\endgroup$
  • $\begingroup$ Welcome to cross-validated. What do you mean by stronger in this case? $\endgroup$ – Skander H. Jan 20 at 18:21
  • $\begingroup$ Basically I just want the same result. Perhaps you can weaken conditions or expand the class of functions. $\endgroup$ – Mark Jan 20 at 21:18
4
$\begingroup$

There are previous results that RNNs are turing complete: Siegelmann 1992, Korsky 2019. (They have some slight technical differences). I found this answer which goes into more technical detail about the proof.

Turing completeness should be a stronger statement than universal approximation, since there are perfectly computable but unbounded or discontinuous functions.

I am aware of the results that any computable real-valued total function is continuous (see here). I don't really have the expertise to comment on this, except to say that I'm still sure turing completeness is still strictly more powerful than universal approximation.

$\endgroup$
  • $\begingroup$ Hmmm, that's the same Siegelmann who later published a paper claiming that NNets can go beyond the Turing limit, a paper which is mathematically unsound and was rebuked by many prominent researchers, and was ignored by the theoretical CS community, but unfortunately keeps coming in various philosophy of ML and philosophy of mind discussions :-( $\endgroup$ – Skander H. Jan 20 at 22:55
  • $\begingroup$ thanks for that note. i didn't read the siegelmann paper in enough detail to verify correctness, but the fact that there exist several other papers proving turing completness for similar architectures (e.g. transformers) inspires confidence in the result. from a very brief skim of the "beyond the turing limit" article, and some literature search, it seems the "unsound" part is reliance on analog computation, or real arithmetic. fwiw some other proofs work with rational arithmetic (but of arbitrary precision). $\endgroup$ – shimao Jan 20 at 23:22
  • $\begingroup$ but then, i expect UAT to also rely on arbitrary precision or real arithmetic, so i don't believe that to be a real objection to the turing completness of RNNs $\endgroup$ – shimao Jan 20 at 23:24
  • $\begingroup$ After reading the wikipedia article on turing complete and turing machines, it seems that you're saying that RNNs can solve any problem that can be solved by comptuters. Is that right? $\endgroup$ – Mark Jan 23 at 4:15
  • $\begingroup$ yes, something like that. $\endgroup$ – shimao Jan 23 at 8:55

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.