On Interaction, Efficiency, and Reversibility

on YouTube ↗45m

" summary

Claim: the Interaction Abstract Machine (IAM) fails the usual invariance thesis — it is not invariant for time or space under natural encodings of Turing machines. Evidence: the Jumping machine gives an exponential speedup over IAM, and CAM gives at most quadratic over Jumping; fixed‑point encodings make multi‑types blow up exponentially. Tools: non‑idempotent intersection (multi) types for time, nested three types and space cam (unchaining, no shared environments, eager GC) for a faithful space measure. Reversibility properties explain some tradeoffs.

AI-written summary · about

" chapters (9)

1. 0:00Interaction efficiency and invariance
2. 5:24Why invariance matters
3. 10:23Lambda calculus size explosion
4. 17:32Interaction machine timing variance
5. 22:10Space efficiency challenges
6. 27:59Cing machine space invariance
7. 32:19Sublinear space and reversibility
8. 40:18Summary and future directions
9. 45:08Q&A