Normalization in type theory: where it is needed, and where not episode artwork

EPISODE · Mar 6, 2020 · 16 MIN

Normalization in type theory: where it is needed, and where not

from Iowa Type Theory Commute · host Aaron Stump

Normalization (every term reaches a normal form via some reduction sequence) is needed essentially in type theory due to the Curry-Howard isomorphism: diverging programs become unsound proofs.  Traditionally, type theorists have also desired normalization or even termination (every term reaches a normal form no matter what reduction sequence is explored in a nondeterministic operational semantics) for conversion checking.  This is the process of confirming that types are equivalent during type checking, which, due to dependent types, can require checking program equivalence.  The latter is usually restricted to just beta-equivalence (where beta-reduction is substitution of argument for input variable when applying a function), because richer notions of program equivalence are usually undecidable.  I have a mini-rant in this episode explaining why this usual requirement of normalization for conversion checking is not sensible.Also I note that you can find the episodes of the podcast organized by chapter on my web page.

Episode metadata supplied by the publisher feed · Published Mar 6, 2020

Embed this episode

Normalization (every term reaches a normal form via some reduction sequence) is needed essentially in type theory due to the Curry-Howard isomorphism: diverging programs become unsound proofs. Traditionally, type theorists have also desired normalization or even termination (every term reaches a normal form no matter what reduction sequence is explored in a nondeterministic operational semantics) for conversion checking. This is the process of confirming that types are equivalent ...

Distinct summary based on available episode metadata or transcript content.

NOW PLAYING

Normalization in type theory: where it is needed, and where not

0:00 16:28

No transcript for this episode yet

We transcribe on demand. Request one and we'll notify you when it's ready — usually under 10 minutes.

No similar episodes found.

No similar podcasts found.

Frequently Asked Questions

How long is this episode of Iowa Type Theory Commute?

This episode is 16 minutes long.

When was this Iowa Type Theory Commute episode published?

This episode was published on March 6, 2020.

Can I download this Iowa Type Theory Commute episode?

Yes. Use the download control on the episode player to save the publisher-provided media file.
URL copied to clipboard!