论文标题
Gödel的T及其抽象复杂性的圆形版本
A circular version of Gödel's T and its abstraction complexity
论文作者
论文摘要
循环和非曲折的证明已成为具有诱导和/或递归形式的系统的金属处理方法越来越流行的工具。在这项工作中，我们调查了gödel系统t的变体CT的表达性，该程序是循环键入的，而不是包括明确的递归组合器。特别是，我们检查了C的抽象复杂性（即类型水平），并表明Gödel原始递归功能可以更简洁地用圆形衍生作用键入，使用的类型精确地比T低于T。我们实际上在两个设置之间提供了逻辑上的对应关系，从而将量化的1型n+1级理论解释为N+1 T级n+1 T级n c and c. vice-n c. and c and c and C. 我们还获得了一些有关圆形“派生”的结果和观点，即基于遗传性可计算功能，类型2的连续性以及对$ \ t $计算相同功能的术语的转换。
Circular and non-wellfounded proofs have become an increasingly popular tool for metalogical treatments of systems with forms of induction and/or recursion. In this work we investigate the expressivity of a variant CT of Gödel's system T where programs are circularly typed, rather than including an explicit recursion combinator. In particular, we examine the abstraction complexity (i.e. type level) of C, and show that the Gödel primitive recursive functionals may be typed more succinctly with circular derivations, using types precisely one level lower than in T. In fact we give a logical correspondence between the two settings, interpreting the quantifier-free type 1 theory of level n+1 T into that of level n C and vice-versa. We also obtain some further results and perspectives on circular 'derivations', namely strong normalisation and confluence, models based on hereditary computable functionals, continuity at type 2, and a translation to terms of $\T$ computing the same functional, at all types.
