Algebras for Deterministic Computation Are Inherently Incomplete

This video presentation from POPL 2025 explores the inherent limitations of algebraic frameworks for deterministic computation. Presented by Balder ten Cate and Tobias Kappé from the University of Amsterdam and Leiden University, the 20-minute talk investigates whether deterministic computation can be captured by a finite set of constructs similar to how Kleene Algebra with Tests (KAT) expresses non-deterministic finite-state computations. Discover why the deterministic fragment of KAT cannot be generated by any finite set of regular control flow operations, extending previous research on traditional control flow operations like sequential composition, if-then-else, and while loops. The presentation builds on their published article and contributes to fundamental understanding of control flow, program algebra, program composition, and expressivity in computer science.