Weak normalization implies strong normalization in pure type systems

The explanation

Start with a small program in the lambda calculus, the core language behind functional programming. Let K be the function that takes x and always returns y. Let Ω be the term (λx.xx)(λx.xx), which applies a function to itself. Running Ω one step gives back Ω exactly, so it never stops. Now look at K applied to Ω. Run the outer call first, and you get y in one step. Run the inner Ω first, and you loop forever. So this term can finish, but it does not have to.

A term is weakly normalizing if some sequence of beta steps reaches a normal form, a term with nothing left to compute. It is strongly normalizing if every such sequence is finite. A beta step is the basic computing move: plug an argument into a function body. Type systems rule out terms like Ω. A pure type system fixes a set of sorts, such as "type" and "kind", and rules for building function types. Related type systems underlie proof assistants such as Coq and Lean.

Barendregt, Geuvers and Klop conjectured that for these systems the two notions agree at the level of the whole system. Geuvers stated it in his 1993 thesisSource 1. Earlier work proved it for restricted families. For example, Sørensen used program translations for some systems without dependent typesSource 2. Those translations need particular rules to be present, so they do not reach every systemSource 3. That is the obstacle: a general system may have no hierarchy of sorts and no tidy rules.

The paper claims the full beta version. In any pure type system, if every legal term in every valid context is weakly normalizing, then every such term is strongly normalizingSource 4. Steps inside type annotations count tooSource 5. No functionality assumption on the axioms or rules is needed. The claim is about the whole system. It does not say that one term with a normal form must always stopSource 6. So K applied to Ω is no counterexample. In a weakly normalizing system it cannot be legal, because Ω has no normal form. The proof first cuts the system down to finitely many sorts and rulesSource 7. It then adapts the Tait–Girard method of reducibility candidatesSource 8. That method attaches to each type a set of terms that are known to terminate.

How sure is this? A computer proof checker called Lean has a formal proof of the main theorem. It covers any specification, arbitrary sorts, nonfunctional axioms and rules, and reduction inside annotations. No specialist review of the paper has been published.

What it doesn't show. This does not say that one single term with a normal form always terminates, and it says nothing about adding eta reduction.