Sebastian Enqvist - Computation by infinite descent made explicit

lmcs:15964 - Logical Methods in Computer Science, June 23, 2026, Volume 22, Issue 2 - https://doi.org/10.46298/lmcs-22(2:32)2026
Computation by infinite descent made explicitArticle

Authors: Sebastian Enqvist

We introduce a non-wellfounded proof system for intuitionistic logic extended with inductive and co-inductive definitions, based on a syntax in which fixpoint formulas are annotated with explicit variables for ordinals. We explore the computational content of this system, in particular we introduce a notion of computability and show that every valid proof is computable. As a consequence, we obtain a normalization result for proofs of what we call finitary formulas. A special case of this result is that every proof of a sequent of the appropriate form represents a unique function on natural numbers. Finally, we derive a categorical model from the proof system and show that least and greatest fixpoint formulas correspond to initial algebras and final coalgebras respectively.


Volume: Volume 22, Issue 2
Published on: June 23, 2026
Accepted on: May 7, 2026
Submitted on: July 1, 2025
Keywords: Logic in Computer Science

Consultation statistics

This page has been seen 314 times.
This article's PDF has been downloaded 79 times.