Fetching the paper…
Reading the bibliography…
We show that autoregressive decoding of a transformer-based language model can realize universal computation, without external intervention or modification of the model's weights.
On the computational power of RNNs
Korsky, S. and Berwick, R. (2019) · 1906
Earlier work this paper cites.
On computable numbers, with an application to the Entscheidungsproblem
Turing, A. (1937) · 1937
Earlier work this paper cites.
Formal reductions of the general combinatorial decision problem
Post, E. (1943) · 1943
Earlier work this paper cites.
A universal Turing machine with two internal states
Shannon, C. (1956) · 1956
Earlier work this paper cites.
On certain formal properties of grammars
Chomsky, N. (1959) · 1959
Earlier work this paper cites.
Linear bounded automata
Myhill, J. (1960) · 1960
Earlier work this paper cites.
The algebraic theory of context free languages
Chomsky, N. and Schützenberger, M. (1963) · 1963
Earlier work this paper cites.
Three theorems on phrase structure grammars of type 1
Landweber, P. (1963) · 1963
Earlier work this paper cites.
Computability of recursive functions
Shepherdson, J. and Sturgis, H. (1963) · 1963
Earlier work this paper cites.
Tag systems and Lag systems
Wang, H. (1963) · 1963
Earlier work this paper cites.
Universality of Tag systems with p = 2 p=2
Cocke, J. and Minsky, M. (1964) · 1964
Earlier work this paper cites.
Classes of languages and linear bounded automata
Kuroda, S.-Y. (1964) · 1964
Earlier work this paper cites.
Formal Languages
Salomaa, A. (1973) · 1973
Earlier work this paper cites.
One-sided and two-sided context in formal grammars
Penttonen, M. (1974) · 1974
Earlier work this paper cites.
Circular automata
Zaiontz, C. (1976) · 1976
Earlier work this paper cites.
Direction independent context-sensitive grammars
Kleijn, H., Penttonen, M., Rozenberg, G., and Salomaa, K. (1984) · 1984
Earlier work this paper cites.
On the computational power of neural nets
Siegelmann, H. and Sontag, E. (1992) · 1992
Earlier work this paper cites.
Small universal circular Post machines
Kudlek, M. and Rogozhin, Y. (2001) · 2001
Cited alongside, same era.
Universality in elementary cellular automata
Cook, M. (2004) · 2004
Cited alongside, same era.
Small universal Turing machines
Neary, T. (2008) · 2008
Cited alongside, same era.
Four small universal Turing machines
Neary, T. and Woods, D. (2009) · 2009
Cited alongside, same era.
The Nature of Computation
Moore, C. and Mertens, S. (2011) · 2011
Cited alongside, same era.
Complexity of small universal Turing machines: A survey
Neary, T. and Woods, D. (2012) · 2012
Cited alongside, same era.
Introduction to the Theory of Computation
Sipser, M. (2013) · 2013
On the Turing completeness of modern neural network architectures
Pérez, J., Marinković, J., and Parceló, P. (2019) · 2019
Later among the works it cites.
On the computational power of transformers and its implications in sequence modeling
Bhattamishra, S., Patel, A., and Goyal, N. (2020) · 2020
Later among the works it cites.
Theoretical limitations of self-attention in neural sequence methods
Hahn, M. (2020) · 2020
Later among the works it cites.
Turing completeness of bounded-precision recurrent neural networks
Chung, S. and Siegelmann, H. (2021) · 2021
Later among the works it cites.
Attention is Turing-complete
Pérez, J., Parceló, P., and Marinković, J. (2021) · 2021
Later among the works it cites.
Thinking like transformers
Weiss, G., Goldberg, Y., and Yahav, E. (2021) · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Neural Turing machines
Graves, A., Wayne, G., and Danihelka, I. (2014) · 2014
Cited alongside, same era.
Learning to transduce with unbounded memory
Grefenstette, E., Hermann, K., Suleyman, M., and Blunsom, P. (2015) · 2015
Cited alongside, same era.
Hybrid computing using a neural network with dynamic external memory
Graves, A., Wayne, G., Reynolds, M., Harley, T., Danihelka, I., Grabska-Barwińska1, A., Colmenarejo, S. G., Grefenstette, E., Ramalho, T., Agapiou, J., Badia1, A. P., Hermann, K. M., Zwols, Y., Ostrovski, G., Cain, A., King, H., Summerfield, C., Blunsom, P., Kavukcuoglu, K., and Hassabis, D. (2016) · 2016
Cited alongside, same era.
Neural GPUs learn algorithms
Kaiser, Ł. and Sutskever, I. (2016) · 2016
Cited alongside, same era.
Neural random-access machines
Kurach, K., Andrychowicz, M., and Sutskever, I. (2016) · 2016
Cited alongside, same era.
Towards revealing the mystery behind chain of thought: A theoretical perspective
Feng, G., Zhang, B., Gu, Y., Ye, H., Ye, D., and Wang, L. (2023) · 2023
Later among the works it cites.
Looped transformers as programmable computers
Giannou, A., Rajput, S., yong Sohn, J., Lee, K., Lee, J. D., and Papailiopoulos, D. (2023) · 2023
Later among the works it cites.
Practical computational power of linear transformers and their recurrent and self-referential extensions
Irie, K., Csordás, R., and Schmidhuber, J. (2023) · 2023
Later among the works it cites.
GPT is becoming a Turing machine: Here are some ways to program it
Jojic, A., Wang, Z., and Jojic, N. (2023) · 2023
Later among the works it cites.
Augmented language models: A survey
Mialon, G., Dessì, R., Lomeli, M., Nalmpantis, C., Pasunuru, R., Raileanu, R., Rozière, B., Schick, T., Dwivedi-Yu, J., Celikyilmaz, A., Grave, E., LeCun, Y., and Scialom, T. (2023) · 2023
Later among the works it cites.
Memory augmented large language models are computationally universal
Schuurmans, D. (2023) · 2023
Later among the works it cites.
Chain of thought empowers transformers to solve inherently serial problems
Li, Z., Liu, H., Zhou, D., and Ma, T. (2024) · 2024
Closest in time.
The illusion of state in state-space models
Merrill, W., Petty, J., and Sabharwal, A. (2024) · 2024
Closest in time.
The expressive power of transformers with chain of thought
Merrill, W. and Sabharwal, A. (2024) · 2024
Closest in time.
Efficient streaming language models with attention sinks
Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis, M. (2024) · 2024
Closest in time.