Gentzen-style monadic translation extends Gödel's System T with new tools

The Gentzen-style monadic translation of Gödel's System T revisited

Logic in Computer Science

Summary

Gödel’s System T is a foundational system in mathematical logic used to represent computations. This paper revisits a way to translate System T terms using a structure called a nucleus that acts like a monad but doesn’t have to follow all monad rules. By picking different nuclei, the authors show how to represent various mathematical concepts such as measures of function size, continuity, and recursion inside System T. They also improve and expand the translation for more data types and provide comparisons with another translation style. This work helps understand and manipulate computational properties within a unified logical framework.

What this means in practice

Authors

Chuangjie Xu

Abstract

We revisit the Gentzen-style monadic translation of Gödel's System T. The translation is parametrized by a nucleus, a monad-like structure that need not satisfy the monad laws. A fundamental theorem of logical relations provides a uniform correctness argument for its instances. By choosing suitable nuclei, we obtain majorants, moduli of pointwise and uniform continuity, internal dialogue trees, and functionals of general bar recursion, all represented by terms of T. The internal dialogue-tree application gives a simpler construction, with correctness established directly using Church-encoded terms. We also extend the translation and its fundamental theorem to sums and finite lists. Finally, we develop the Kuroda-style translation and its continuity instance, comparing the moduli obtained with those of the Gentzen-style translation.