On normalization for the typed λ-calculus

Add to your list(s) Download to your calendar using vCal

• Simon Castellan
• Friday 11 November 2016, 10:45-11:45
• Rainbow Room (FS07), Computer Laboratory.

If you have a question about this talk, please contact Ian Orton.

In this talk, I will investigate normalization proof for several typed λ-calculi on their relationship with logic.

I will start with the simply-typed λ-calculus and the “classic” termination proof using realizability. I will discuss the computational meaning of this proof in terms of normalization by evaluation (Following recent work by Gabriel Scherer) and mention the expressivity of the simply-typed λ-calculus in terms of ordinal complexity.

I will then move on to Gödel’s system T, extend the proof and present the connection with PA1 , Peano’s arithmetic and how to deduce from strong normalization of T, consistency of PA_1. I will (try to) comment on the link between this consistency proof and Gentzen’s one using transfinite induction. Finally, I move to Girard’s system F and the link with PA2 .

I will assume basic familarity with the calculus in question (simply-typed, T, F) and the logics associated (Propositional logical, PA1 , PA2).

This talk is part of the Logic & Semantics for Dummies series.

This talk is included in these lists:

• Logic & Semantics for Dummies
• Rainbow Room (FS07), Computer Laboratory
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.