Iowa Type Theory Commute

Aaron Stump

Aaron Stump talks about type theory, computational logic, and related topics in Computer Science on his short commute.

  1. 22 AUG.

    Schematic Affine Recursion, Oh My!

    To 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) plus structural recursion does not enforce termination, even if you restrict the recursor so that the function to be iterated is closed when you reduce ("closed at reduction").  You have to restrict it so that recursion terms are disallowed entirely unless the function to be iterated is closed ("closed at construction").  But this prevents higher-order functions like map, which need to repeat a computation involving a variable f to be mapped over the elements of a list.  The solution is to allow schematic definition of terms, using schema variables ranging over closed terms.

    19 min

  2. 19 AUG.

    The Stunner: Linear System T is Diverging!

    In 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 revisited", by Alves, Fernández, Florido, and Mackie.  Linear System T is diverging, as they reveal through a short but clever example.  It is even diverging if one requires that the iterator can only be reduced when the function to be iterated is closed (no free variables).  This extraordinary observation does not sink Victor's idea of basing type theory on a terminating untyped core language, but it does sink the specific language he and I were thinking about, namely affine lambda calculus plus structural recursion. My notes are here.

    21 min

  3. 1 AUG.

    Terminating Computation First?

    In 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 erect as exotic a type system as one wishes.  By enforcing termination already for the untyped language, we no longer have to make the type system do the heavy work of enforcing termination.

    11 min

  4. 12 MAJ

    Correction: the Correct Author of the Proof from Last Episode, and an AI flop

    I 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 about this.

    7 min

  5. 5 MAJ

    Krivine's Proof of FD, Using Intersection Types

    Krivine's book (Section 4.2) has a proof of the Finite Developments Theorem, based on intersection types.  I discuss this proof in this episode.

    22 min

  6. 16 APR.

    A Measure-Based Proof of Finite Developments

    I discuss the paper "A Direct Proof of the Finite Developments Theorem", by Roel de Vrijer.  See also the write-up at my blog.

    23 min

  7. 27 MARS

    Introduction to the Finite Developments Theorem

    The finite developments theorem in pure lambda calculus says that if you select as set of redexes in a lambda term and reduce only those and their residuals (redexes that can be traced back as existing in the original set), then this process will always terminate.  In this episode, I discuss the theorem and why I got interested in it.

    16 min

  8. 31 JAN.

    Nominal Isabelle/HOL

    In this episode, I discuss the paper Nominal Techniques in Isabelle/HOL, by Christian Urban.  This paper shows how to reason with terms modulo alpha-equivalence, using ideas from nominal logic.  The basic idea is that instead of renamings, one works with permutations of names.

    16 min
Visa alla (178)

Betyg och recensioner

5
av 5
3 betyg

Om

Aaron Stump talks about type theory, computational logic, and related topics in Computer Science on his short commute.

Information

  • Skapad av
    Aaron Stump
  • Aktiva år
    2019 - 2025
  • Avsnitt
    178
  • Åldersgräns
    Barnvänligt
  • Copyright
    © 2025 Iowa Type Theory Commute
  • Programmets webbplats
    Iowa Type Theory Commute

Du kanske också gillar