Skip to content
The methodOpen data
Back to the collection

On the Turing Completeness of Modern Neural Network Architectures

Jorge Pérez, Javier Marinković, Pablo Barceló

2019 · arXiv

Machine learningLanguage models
Read the paper
HN score
1
Mentions
9
Readers
8
Months
8
What’s in a score?

From the abstract

Alternatives to recurrent neural networks, in particular, architectures based on attention or convolutions, have been gaining momentum for processing input sequences. In spite of their relevance, the computational properties of these alternatives have not yet been fully explored. We study the computational power of two of the most paradigmatic architectures exemplifying these mechanisms: the Transformer (Vaswani et al., 2017) and the Neural GPU (Kaiser & Sutskever, 2016). We show both models to be Turing complete exclusively based on their capacity to compute and access internal dense representations of the data. In particular, neither the Transformer nor the Neural GPU requires access to an external memory to become Turing complete. Our study also reveals some minimal sets of elements needed to obtain these completeness results.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

9 selected excerpts · 9 total mentions

bhntr3
Recommendation · rule
Here's an interesting paper on the topic. It seems that only some NN architectures are turing complete: https://arxiv.org/pdf/1901.03429.pdf To the essence of what I think the original question is asking: It seems possible (due to the turing completeness of some NN architectures) that a language model could learn a sub-network that was a turing complete computational framework + problem solver and then use that to solve problems in natural language. But it also seems highly unlikely that it would actually play out that way. The linked paper has a nice summary of attempts to build neural nets that learn algorithms. It seems this more direct approach would be likely to…
Read the full comment
yield a result faster than waiting for such a capability to emerge in GPT-12 or something. Of course most ML models execute from within a turing complete programming language/execution environment anyway. If we want to solve math problems, it might be easier to train a model to translate natural language into a more formal definition (afaik this is still very hard) and then hand off the formal definition of the problem to an automated theorem prover. After all, being turing complete doesn't make all problems solvable or tractable from a run time / memory perspective and that's probably the bigger bottleneck when it comes to solving hard math problems.
Original comment Is This a Turing Machine?
rlupi
Neutral mention · rule
> No AI can code in Lean 4 reliably I wonder if this is due to the nature of the language. Lean 4 lets you redefine its syntax in ways that most other languages do not allow[1], so effectively you are dealing with a recursive language, that could require a Touring complete token representation system. [1] https://leanprover-community.github.io/lean4-metaprogramming... What other language lets you redefine the meaning of digits? The mix of syntax + macros + elaboration makes it really flexible, but hard to treat reliably. LLMs based on transformers are not Touring complete (nitpick: they are but only if you use arbitrary precision math, which is not the case in practical implementation https://arxiv.org/abs/1901.03429).
Original comment Efficient Reasoning with Hidden Thinking
MacsHeadroom
Neutral mention · rule
Transformers are turing complete: https://arxiv.org/abs/1901.03429 Additionally, Transformers are RNNs: https://arxiv.org/abs/2006.16236 Transformers are turing complete RNNs, as are the Neocortex. There are differences like spiking vs non-spiking neurons, universal vs non-universal activation, the effects of brain waves, bicameralism, etc. But these differences may or may not be important depending on the topic of discussion. Additionally, the differences increasingly disappear as transformers are increasingly augmented with functionally equivalent systems.
Original comment There Is No A.I
naasking
Neutral mention · rule
> I must have missed the part when it started doing anything algorithmically. I thought it’s applied statistics, with all the consequences of that. This is a common misunderstanding. Transformers are actually Turing complete: * On the Turing Completeness of Modern Neural Network Architectures, https://arxiv.org/abs/1901.03429 * On the Computational Power of Transformers and its Implications in Sequence Modeling, https://arxiv.org/abs/2006.09286
Original comment GPT-4
fasterik
Neutral mention · rule
Modern neural network architectures are Turing complete [1]. So I don't see any argument for a limit in principle unless you are arguing that a Turing machine can't achieve language understanding. If that's what you're saying, then I wonder who is espousing mysticism here. [1] https://arxiv.org/abs/1901.03429
Original comment Petals: Run 100B+ language models at home bit-torrent style
ly3xqhl8g9
Neutral mention · rule
Precisely, fun is the operative word. As I was writing I was thinking that perhaps you would still need to run client-side non-layout JS, however, "attention is all you need": it seems that there are some architectures for Turing complete neural networks [1]. I wouldn't worry about performance: Nvidia breaks world records with H100 [2], Intel is going for 6 GHz processors [3], for performance you just have to be patient. [1] 2019, Jorge Pérez et. al, On the Turing Completeness of Modern Neural Network Architectures, https://arxiv.org/pdf/1901.03429.pdf [2] https://blogs.nvidia.com/blog/2022/09/08/hopper-mlperf-infer... [3] https://www.tomshardware.com/news/intel-teases-8-ghz-raptor-...
Original comment Ladybird: A new cross-platform browser project
tsimionescu
Neutral mention · rule
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…
Read the full comment
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 [1] https://en.wikipedia.org/wiki/Universal_approximation_theore...
Original comment LaMDA is not sentient
riku_iki
Neutral mention · rule
Transformer is a function from seq of symbols to seq of symbols. For example, truth table is exactly similar kind of function from variables to [True, False] alphabet. Transformer can represent some very complex logical operations, and per this article is turing complete: https://arxiv.org/abs/1901.03429, meaning any computable function, including theorem prover can be represented as transformer. Another question is if it is feasible/viable/rational to build transformer for this? My intuition says: no.
Original comment Graph Representations for Higher-Order Logic and Theorem Proving (2019)
naasking
Neutral mention · rule
* On the Turing Completeness of Modern Neural Network Architectures, https://arxiv.org/abs/1901.03429 * On the Computational Power of Transformers and its Implications in Sequence Modeling, https://arxiv.org/abs/2006.09286
Original comment Caricaturing Noam Chomsky

Keep following the thread.

More in Machine learning

More from the same topics.