Transformer Expressivity and Formal Logic

Explore a thought-provoking lecture on the relationship between transformers and formal logic systems. Delve into David Chiang's research findings, both published and unpublished, that connect transformers to first-order logic, linear temporal logic, and their counting extensions. Gain insights into the capabilities and limitations of transformers as a computational model, and understand how factors like depth impact their expressivity. This 46-minute talk, presented at the Simons Institute, offers a deep dive into the theoretical underpinnings of transformer models and their connections to established logical frameworks.