About whether transformers being Turing complete means LLMs can learn real algorithms.
Has this happened?
Yes 62 (61%)Not sure 29 (28%)No 11 (11%)
Votes cast 1–2 October 2026: 100,590 votes from 9,694 people.
Hacker News has set AI a lot of challenges over the years. Which ones has it met?
About whether transformers being Turing complete means LLMs can learn real algorithms.
Votes cast 1–2 October 2026: 100,590 votes from 9,694 people.
Turing Completeness is an incredibly low bar and it doesn't undermine this criticism. Conway's Game of Life is Turing Complete, but try writing modern software with it. That Transformers can express arbitrary programs in principle doesn't mean SGD can find them. Following gradients only works when the data being modelled lies on a continuous manifold, otherwise it will just give a statistical approximation at best. All sorts of data we care about lie in topological spaces with no metric: algorithms in computer science, symbolic reasoning in math, etc. If SGD worked for these cases LLMs would push research boundaries in maths and physics or at the very least have a good go at Chollet's ARC challenge, which is trivial for humans. Unfortunately, they can't do this because SGD makes the wrong assumption about how to search for programs in discrete/symbolic/topological spaces.