4 ms·
I think the point here is that all architectures can execute a certain type of program. An RNN maps to a finite state automaton, and this is an attempt at showi
by phreeza 5y ago
I think the point here is that all architectures can execute a certain type of program. An RNN maps to a finite state automaton, and this is an attempt at showing what the natural class of programs a transformer can implement is.
- siekmanj 5y agoActually, I think it is conventional neural networks which can only approximate finite state machines. RNNs are (in theory, not so much in practice) Turing complete.
- thomasahle 5y ago> RNNs are Turing complete. Turing completeness requires access to unlimited read/write memory. RNNs only have a fixed dimensional state. I guess I'm theory that starte is continuous, but it has to be a pretty optimistic model that assumes we can handle unbounded data like that.
- deleted 5y ago[deleted]
- peytn 5y agoIntuitively I think as long as your activation function is sufficiently expressive (e.g. not a step function or something), you should be go to go in theory since that’s what you’re feeding back. Might take a while.
- thomasahle 5y agoThe word I was looking for is "robust". Any realistic model must be able to accept tiny perturbations (like Gaussian noise) of the vectors, since that's how floating arithmetic works. An RNN can't be robustly Turing complete.