- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies the minimal requirements for an autoregressive generative model to be Turing-complete, building on the many existing Turing-completeness results of specific neural architectures such as transformers and RNNs. The authors find that even a single neuron (with threshold activation for discrete computation and many different non-linear functions for continuous computation) suffices for Turing completeness. To prove this, the authors show how to construct a single neuron with sufficiently many inputs that can simulate any given circuit, and rely on an interesting application of a Sidon set. The paper also discusses the implications of the result on learnability with autoregressive thoughts (chain of thought) and the optimality of the neuron size.
Critical strengths
- The paper asks the innovative question of the minimal set of capabilities an architecture requires for Turing completeness with autoregression. This abstracts away any specific architecture and shows that, in a sense, Turing completeness is a somewhat natural consequence of autoregression.
- The paper is easy to follow and well written. The notation is clear, the claims well-supported and presented understandably.
- I think the methodology is novel and interesting, and could be of use to much follow-up work.
- The authors not only derive the expressivity results but also discuss the implications for learnability.
- The experiments complement the theoretical results well.
Critical weaknesses
None
Questions for authors
- Your result sits on one end of the spectrum with just one neuron, and, e.g., Turing completeness results for transformers are on the other end with a very specific architecture. Do you think we can also gain any insights into the expressivity of small fixed-size circuits (larger than a single neuron)?