Final Notes on Computation

We examine some curiosities that tie the ideas in this series together. First, how can we write a grammar for the syntax of regular expressions themselves? That is, what are the rules for a valid regex? Likewise, how can we write a grammar for the syntax of grammar definitions themselves? (The answers to these are surprising!) Finally, how does the historical division between Turing machine and lambda calculus relate to the modern division between imperative and functional programming?

(Note: The grammar-grammar shown in this screencast isn't actually a grammar for itself for a trivial reason: it uses double quotes for literals, but only describes a syntax using single quotes. Changing the quotes to ''' would correct the problem, though that syntax is less clear to human readers. This doesn't impact the conclusions drawn.)