Hacker News Reader

Comment by 0-_-0 | Hacker News Reader

This is nice, however simple fully connected or convolutional networks can encode computer programs too. In fact, the hope for RNNs was that they will learn computer programs, but due to the weirdness of neural network training that never happened in practice to a satisfying degree. So finding a programming model for Transformers is not necessarily as practical as it first seems, since there's no guarantee that they will learn these programs from data.

View on HN

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.

Actually, 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.

> 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.

Intuitively 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.

The 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.

Reply on news.ycombinator.com