Iowa Type Theory Commute
de Aaron Stump
Episódio mais recente
Great paper: Complete and Easy Bidirectional Typechecking for…
Great paper: Complete and Easy Bidirectional Typechecking for…
Sobre este podcast
Aaron Stump talks about type theory, computational logic, and related topics in Computer Science on his short commute.
Episódios
Os 20 episódios mais recentes de 192
- Great paper: Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism · 18 min · Temporada 8 Episódio 2I start discussing this great paper by Dunfield and Krishnaswami, about how to extend a particular approach to type inference to handle polymorphism.
- Autoformalization of Fermat's Last Theorem · 14 min · Temporada 8 Episódio 1In this episode, I reflect on the recent announcement that Anthropic researchers have autoformalized the proof of Fermat's Last Theorem. That is, they instructed an LLM to create…
- A Fireball of Alpha · 20 min · Temporada 7 Episódio 12I talk about my efforts to formalize lambda-calculus with named variables and explicit alpha-equivalence, as originally proposed by Church. One reason to do that, besides just a…
- Solving Quadratic Word Equations · 23 min · Temporada 7 Episódio 11A system of word equations is called quadratic if no variable occurs more than twice in it. There is an interesting simple algorithm to solve quadratic systems of word equations…
- A little bit about word equations · 17 min · Temporada 7 Episódio 10The problem of word equations is a rather storied one, including frustrated connections to Hilbert's Tenth problem. Word equations relate expressions consisting of concatenations…
- Coercive subtyping and coherence · 21 min · Temporada 7 Episódio 9In this episode, I give further arguments in favor of coercive subtyping from a software-engineering perspective. I also explain the critical concept of coherence.
- A Strange Deal · 3 min · Temporada 7 Episódio 7The Curry-Howard isomorphism for the law of excluded middle, as a radio drama. I first saw a version of this story performed by Phil Wadler and Frank Pfenning (wearing fake…
- Great paper: The Calculated Typer · 24 min · Temporada 7 Episódio 6I discuss a nice paper I quite enjoyed reading, called The Calculated Typer, by Garby, Bahr, and Hutton. The authors take a very nice general look at the specification of a type…
- Double-negation translations and CPS conversion, part 2 · 14 min · Temporada 7 Episódio 5In this episode, I talk about the control operator callcc, and how it is implemented during compilation using continuation-passing style (CPS). I sketch how CPS conversion…
- Double-negation translations and CPS conversion, part 1 · 14 min · Temporada 7 Episódio 4In this episode, I talk about a somewhat more advanced case of the Curry-Howard isomorphism (the connection between logic and programming languages where formulas in logic are…
- What are commuting conversions in proof theory? · 22 min · Temporada 7 Episódio 3Commuting conversions are transformations on proofs in natural deduction, that move certain stuck inferences out of the way, so that the normal detour reductions (which…
- What is Control Flow Analysis for Lambda Calculus? · 19 min · Temporada 7 Episódio 2I am currently on a frolic into the literature on Control Flow Analysis (CFA), and discuss what this is, for pure lambda calculus. A wonderful reference for this is this paper by…
- Measure Functions and Termination of STLC · 22 min · Temporada 7 Episódio 1In this episode, I talk about what we should consider to be a measure function. Such functions can be used to show termination of some process or program, by assigning a measure…
- Schematic Affine Recursion, Oh My! · 19 min · Temporada 6 Episódio 12To solve the problem raised in the last episode, I propose schematic affine recursion. We saw that affine lambda calculus (where lambda-bound variables are used at most once)…
- The Stunner: Linear System T is Diverging! · 21 min · Temporada 6 Episódio 11In this episode, I shoot down last episode's proposal -- at least in the version I discussed -- based on an amazing observation from an astonishing paper, "Gödel’s system T…
- Terminating Computation First? · 11 min · Temporada 6 Episódio 10In this episode, I discuss an intriguing idea proposed by Victor Taelin, to base a logically sound type theory on an untyped but terminating language, upon which one may then…
- Correction: the Correct Author of the Proof from Last Episode, and an AI flop · 7 min · Temporada 6 Episódio 9I correct what I said in the last episode about the author of the proof of FD from last episode based on intersection types. I also describe AI flopping when I ask it a question…
- Krivine's Proof of FD, Using Intersection Types · 22 min · Temporada 6 Episódio 8Krivine's book (Section 4.2) has a proof of the Finite Developments Theorem, based on intersection types. I discuss this proof in this episode.
- A Measure-Based Proof of Finite Developments · 23 min · Temporada 6 Episódio 7I discuss the paper "A Direct Proof of the Finite Developments Theorem", by Roel de Vrijer. See also the write-up at my blog.








