2 ms·
That part about "meaningful computations" was indeed a bad phrasing, and, ironically, quite meaningless. Still, it's important to note that "ANNs are Turing Co
by tsimionescu 4y ago
That part about "meaningful computations" was indeed a bad phrasing, and, ironically, quite meaningless.
Still, it's important to note that "ANNs are Turing Complete" actually means "particular classes of ANNs are Turing Complete" - that is, for any Turing Machine, you can construct an equivalent ANN from that class. Here is a paper [0] showing this for the Transformer architecture that is quite relevant to GPT-3 (not sure if LaMDA is also based on this). Note that even here, there are some caveats - you have to use a positional encoding, and the Transformer must have some particular layers.
Still, this doesn't mean that a particular ANN (by which I mean, the result of training, like the copy of GPT-3 that is accessible via APIs) is Turing Complete, or even that the training mechanism used is Turing Complete. The proof in that paper only shows that for every TM there exists a corresponding Transformer ANN that produces the same output for the same input. That doesn't mean you can train this ANN based on backprop/gradient descent. Even more, it definitely doesn't mean GPT-3 itself can perform any computation, in the sense that my CPU can be programmed to, or produce any program in the sense that a C compiler can.
Note that even the universal function approximator result works the same way - it shows that for any (continuous and differentiable in at least one point) function there exists an ANN with certain properties that approximates it to arbitrary precision [1]. This doesn't mean that such an ANN can actually be constructed using backpropagation or other known training methods, from any input.
It also means that there isn't necessarily any ANN that can arbitrarily approximate a non-continuous function, such as tan(x) or f(x) = {1 for x >= 0, 0 for x < 0}, or continuous everywhere but differentiable nowhere functions like the Weierstrass function.
[0] https://arxiv.org/pdf/1901.03429.pdf https://arxiv.org/pdf/1901.03429.pdf
[1] https://en.wikipedia.org/wiki/Universal_approximation_theorem#Arbitrary-depth_case https://en.wikipedia.org/wiki/Universal_approximation_theore...