Built on

A. M. Turing, “Computability and λ \lambda -definability,” The Journal of Symbolic Logic
1937
Earlier work this paper cites.
H. Wang, “A variant to turing’s theory of computing machines,” Journal of the ACM (JACM)
1957
Earlier work this paper cites.
K. Hornik, M. Stinchcombe, and H. White, “Multilayer feedforward networks are universal approximators,” Neural networks
1989
Earlier work this paper cites.
H. T. Siegelmann and E. D. Sontag, “On the computational power of neural nets,” in Proceedings of the fifth annual workshop on Computational learning theory
1992
Earlier work this paper cites.
J. P. Neto, H. T. Siegelmann, J. F. Costa, and C. S. Araujo, “Turing universality of neural nets (revisited),” in Computer Aided Systems Theory—EUROCAST’97: A Selection of Papers from the 6th International Workshop on Computer Aided Systems Theory Las Palmas de Gran Canaria, Spain, February 24–28, 1997 Proceedings 6
1997
Earlier work this paper cites.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” Advances in neural information processing systems
2017
Earlier work this paper cites.
P. J. Liu, M. Saleh, E. Pot, B. Goodrich, R. Sepassi, L. Kaiser, and N. Shazeer, “Generating wikipedia by summarizing long sequences,” arXiv preprint arXiv:1801.10198
Original
2018
Earlier work this paper cites.

Similar

A. Radford, K. Narasimhan, T. Salimans, I. Sutskever, et al
2018
Cited alongside, same era.
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” arXiv preprint arXiv:1810.04805
Original
2018
Cited alongside, same era.
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al
2019
Cited alongside, same era.
J. Pérez, J. Marinković, and P. Barceló, “On the turing completeness of modern neural network architectures,” arXiv preprint arXiv:1901.03429
Original
2019
Cited alongside, same era.
C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, and S. Kumar, “Are transformers universal approximators of sequence-to-sequence functions?,” arXiv preprint arXiv:1912.10077
Original
2019
Cited alongside, same era.

Then

S. Bhattamishra, A. Patel, and N. Goyal, “On the computational power of transformers and its implications in sequence modeling,” arXiv preprint arXiv:2006.09286
Original
2020
Later among the works it cites.
M. Hahn, “Theoretical limitations of self-attention in neural sequence models,” Transactions of the Association for Computational Linguistics
2020
Later among the works it cites.
J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou, “Chain of thought prompting elicits reasoning in large language models,” arXiv preprint arXiv:2201.11903
Original
2022
Later among the works it cites.
M. C. Rillig, M. Ågerstrand, M. Bi, K. A. Gould, and U. Sauerland, “Risks and benefits of large language models for the environment,” Environmental Science & Technology
2023
Closest in time.
OpenAI, “Gpt-4 technical report,” ArXiv

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2023

How Powerful are Decoder-Only Transformer Neural Models?

Roberts, Jesse

Understand

In this article we prove that the general transformer neural model undergirding modern large language models (LLMs) is Turing complete under reasonable assumptions.

This is the first work to directly address the Turing completeness of the underlying technology employed in GPT-x as past work has focused on the more expressive, full auto-encoder transformer architecture.
From this theoretical analysis, we show that the sparsity/compressibility of the word embedding is an important consideration for Turing completeness to hold.
We also show that Transformers are are a variant of B machines studied by Hao Wang.

Built on

A. M. Turing, “Computability and λ \lambda -definability,” The Journal of Symbolic Logic
1937
Earlier work this paper cites.
H. Wang, “A variant to turing’s theory of computing machines,” Journal of the ACM (JACM)
1957
Earlier work this paper cites.
K. Hornik, M. Stinchcombe, and H. White, “Multilayer feedforward networks are universal approximators,” Neural networks
1989
Earlier work this paper cites.
H. T. Siegelmann and E. D. Sontag, “On the computational power of neural nets,” in Proceedings of the fifth annual workshop on Computational learning theory
1992
Earlier work this paper cites.
J. P. Neto, H. T. Siegelmann, J. F. Costa, and C. S. Araujo, “Turing universality of neural nets (revisited),” in Computer Aided Systems Theory—EUROCAST’97: A Selection of Papers from the 6th International Workshop on Computer Aided Systems Theory Las Palmas de Gran Canaria, Spain, February 24–28, 1997 Proceedings 6
1997
Earlier work this paper cites.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” Advances in neural information processing systems
2017
Earlier work this paper cites.
P. J. Liu, M. Saleh, E. Pot, B. Goodrich, R. Sepassi, L. Kaiser, and N. Shazeer, “Generating wikipedia by summarizing long sequences,” arXiv preprint arXiv:1801.10198
Original
2018
Earlier work this paper cites.

Similar

A. Radford, K. Narasimhan, T. Salimans, I. Sutskever, et al
2018
Cited alongside, same era.
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” arXiv preprint arXiv:1810.04805
Original
2018
Cited alongside, same era.
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al
2019
Cited alongside, same era.
J. Pérez, J. Marinković, and P. Barceló, “On the turing completeness of modern neural network architectures,” arXiv preprint arXiv:1901.03429
Original
2019
Cited alongside, same era.
C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, and S. Kumar, “Are transformers universal approximators of sequence-to-sequence functions?,” arXiv preprint arXiv:1912.10077
Original
2019
Cited alongside, same era.

Then

S. Bhattamishra, A. Patel, and N. Goyal, “On the computational power of transformers and its implications in sequence modeling,” arXiv preprint arXiv:2006.09286
Original
2020
Later among the works it cites.
M. Hahn, “Theoretical limitations of self-attention in neural sequence models,” Transactions of the Association for Computational Linguistics
2020
Later among the works it cites.
J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou, “Chain of thought prompting elicits reasoning in large language models,” arXiv preprint arXiv:2201.11903
Original
2022
Later among the works it cites.
M. C. Rillig, M. Ågerstrand, M. Bi, K. A. Gould, and U. Sauerland, “Risks and benefits of large language models for the environment,” Environmental Science & Technology
2023
Closest in time.
OpenAI, “Gpt-4 technical report,” ArXiv

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al

2020

Cited alongside, same era.

Original

2023

Closest in time.

D. Schuurmans, “Memory augmented large language models are computationally universal,” arXiv preprint arXiv:2301.04589

Original

2023

Closest in time.