Are transformer LLMs equivalent to Turing machines or not? Spoiler: they are, because Franz Nowak (the guest of this episode) and colleagues proved this in their latest paper!
We talk with Franz about RNNs, transformer encoders, decoders (with CoT), so if you're like me and always wanted some clarity on the computational expressivity of deep learning architectures -- and the Chomsky hierarchy -- have a listen! 🎙️
AI Coffee Break Merch! 🛍️ https://aicoffeebreak.creator-spring.com/
📚 ACL tutorial on Computational Expressivity of LLMs: https://acl2024.ivia.ch/
🗂️ Franz Nowak: https://franznowak.github.io/
📃 Nowak, F., Svete, A., Butoi, A. and Cotterell, R., 2024. On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning. https://arxiv.org/abs/2406.14197
Outline:
00:00 Transformers are Turing complete!
00:52 Franz Nowak Intro
03:14 The Chomsky Hierarchy
07:49 Is my laptop Turing complete?
09:27 Transformer encoders
10:19 Transformer decoders
12:26 RNNs are Turing complete
13:52 LLM with CoT
17:51 Learnability
21:11 Sparsity of human proofs
25:59 Why care about theory?
Thanks to our Patrons who support us in Tier 2, 3, 4: 🙏
Dres. Trost GbR, Siltax, Vignesh Valliappan, Michael, Sunny Dhiana, Andy Ma
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
🔥 Optionally, pay us a coffee to help with our Coffee Bean production! ☕
Patreon: https://www.patreon.com/AICoffeeBreak
Ko-fi: https://ko-fi.com/aicoffeebreak
Join this channel to get access to perks:
https://www.youtube.com/channel/UCobqgqE4i5Kf7wrxRxhToQA/join
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
🔗 Links:
AICoffeeBreakQuiz: https://www.youtube.com/c/AICoffeeBreak/community
Twitter: https://twitter.com/AICoffeeBreak
Reddit: https://www.reddit.com/r/AICoffeeBreak/
YouTube: https://www.youtube.com/AICoffeeBreak
#AICoffeeBreak #MsCoffeeBean #MachineLearning #AI #research
Music 🎵 : Just Breathing (Instrumental) - NEFFEX