The Turing machine gives us a way to compute anything that is mathematically computable. But it turns out this is too powerful to describe the computations performed by a human mind! Noam Chomsky built on Turing's work by creating a hierarchy of computations - from the simplest possible computations to the most complex. In this video, we'll examine how this hierarchy of computational complexity may explain certain aspects of our cognition.



0:00 - Intro
1:00 - Noam Chomsky
2:32 - Formal grammars
3:40 - The simplest grammars
5:13 - Pushdown stack
7:14 - The Chomsky hierarchy
11:12 - Finite state machines
16:41 - Examples of finite state machines
20:30 - Applying it to human cognition
25:59 - Wrapping up
26:59 - Key concepts

Sources:
Chomsky (1956). Three models for the description of language. https://doi.org/10.1109/TIT.1956.1056813
Gold (1967). Language identification in the limit. https://doi.org/10.1016/S0019-9958(67...
Heinz & Idsardi (2011). Sentence and word complexity. https://www.science.org/doi/abs/10.11...

Check out Computerphile (   / computerphile  ) - they have a ton of awesome videos on computer science, including several great videos about formal grammars, finite state machines, and Noam Chomsky!