Attention is Turing Complete.


Alternatives to recurrent neural networks, in particular, architectures based on self-attention, are gaining momentum for processing input sequences. In spite of their relevance, the computational properties of such networks have not yet been fully explored. We study the computational power of the Transformer, one of the most paradigmatic architectures exemplifying self-attention. We show that the Transformer with hard-attention is Turing complete exclusively based on their capacity to compute and access internal dense representations of the data. Our study also reveals some minimal sets of elements needed to obtain this completeness result.

Date: May 22, 2024 at 15:00:00 h
Venue: Sala de Seminario John Von Neumann, CMM, Beauchef 851, Torre Norte, Piso 7.
Speaker: Javier Marinkovic
Affiliation: Universidad de Chile
Coordinator: José Verschae
More info at:
Event website

Posted on May 22, 2024 in ACGO, Seminars