Expressivity of Transformers: Logic, Circuits, and Formal Languages

A major advancement in language modeling is the use of the transformer architecture. But what problems can transformers solve, what problems can they not solve, and how can we prove it? This course examines the expressivity of transformers through the lens of computability and complexity theory. We situate transformers within the landscape of automata, boolean circuits, and formal logics. We discuss what is currently known about transformers’ capabilities and limitations, address practical implications for NLP, and identify directions for future work. Participants gain a comprehensive understanding of transformers’ expressive power.

Organizers

David Chiang
David Chiang
University of Notre Dame
dchiang[æt]nd.edu

Lena Strobl
Lena Strobl
Umeå University
lena.strobl[æt]umu.se
Jon Rawski
Jon Rawski
MIT/San Jose State University
jon.rawski[æt]sjsu.edu

Andy J Yang
Andy J Yang
University of Notre Dame
ayang4[æt]nd.edu

Course Schedule

Monday, July 29 – Friday, August 2
5.00pm – 6.30pm

Location: Aula Jean Monnet (the big auditorium)

Course Materials

Lecture Notes

Daily Slides

License

All course materials are licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0).
You are free to share and adapt the materials with proper attribution.