How hard can it be! Practical uses of complexity theory
summary
A sequence of small machines gets built and tested: a finite state automaton that accepts alternating cat/dog petting and works for that rule; a pushdown automaton that uses a stack to verify the same number of cats then dogs and succeeds; a linear bounded Turing machine that adds a tape to handle cats dogs turtles and still decides validity; moving to an unrestricted Turing machine exposes undecidable checks like predicting whether an arbitrary petting process ever stops.
AI-written summary · about
chapters (10)
- 0:00Start
- 0:35HOW HARD CAN IT BE? Practical uses of complexity theory
- 0:53PICTURE THIS
- 3:30They first must pet a specific number of cats and then the same number of dogs!
- 11:52LITTLE RECAP
- 12:40WHAT IS A LANGUAGE?
- 15:22VALIDATION
- 17:13EXPRESSIVE POWER
- 17:38REGULAR GRAMMAR REGULAR EXPRESSION
- 19:30AVOIDING WORK
related talks
20mSimulating computational complexity
50mA Relational Exploration of the Chomsky Hierarchy
01h 01mUnderstanding Transformers through the Lens of Logic and Automata
45mThe Conscious Turing Machine (CTM), a formally defined Theoretical model of Consciousness
20mSmale’s 18th Problem and Intelligence Science
18mGuiding machine design using insights from simple sandboxes
39mComputational Thinking on Learning Models
10mSATisfying answers to difficult questions!