On the Turing Completeness of Modern Neural Network Architectures

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

rlupiFeb 4, 2025View on HNParent context

It's gibberish. For one thing... https://arxiv.org/abs/1901.03429

benzibleSep 23, 2024View on HNParent context

2019 version which includes the Neural GPU: https://arxiv.org/abs/1901.03429

gwernJun 14, 2023View on HNParent context

It's a well known property: https://arxiv.org/abs/1901.03429

naaskingApr 22, 2023View on HNParent context

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…

MacsHeadroomApr 22, 2023View on HNParent context

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

naaskingMar 15, 2023View on HNParent context

* 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

naaskingMar 12, 2023View on HNParent context

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]…

fasterikJan 10, 2023View on HNParent context

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…

ly3xqhl8g9Sep 12, 2022View on HNParent context

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…

tsimionescuJun 13, 2022View on HNParent context

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…

riku_ikiSep 6, 2020View on HNParent context

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…

bhntr3Jul 3, 2020View on HNParent context