A Relational Exploration of the Chomsky Hierarchy
summary
miniKanren implementation claims to encode deterministic and non-deterministic finite automata plus push‑down automata and Turing Machines and it actually runs: acceptors become generators of strings in the language (and of non-members) and reversing relations produces internal structures like stacks. Tests compare NFA generation to DFA answers to show equivalence; examples include an NFA that generates accepted strings, a PDA manipulating an explicit list stack, and an automatic search that synthesizes a Y combinator and quines — all demonstrated working.
AI-written summary · about
chapters (5)
- 0:00Start
- 17:50finding automaton
- 25:47write your own determinist non-deterministic finite automaton
- 39:33combinatory logic
- 48:22the z combinator
related talks
44mA Vision for Relational Programming in miniKanren
21mHow hard can it be! Practical uses of complexity theory
23mImproving stableKanren’s Backward Compatibility
43mPost Functional
12mComputation with sequences of neuronal assemblies
21mNeural Turing Machines: Perils and Promise
18mGuiding machine design using insights from simple sandboxes
01h 01mUnderstanding Transformers through the Lens of Logic and Automata