Subrecursion and lambda representation over free algebras
Subrecursion and lambda representation over free algebras
复制标题
自由代数上的子递归和 lambda 表示
DOI：
10.1007/978-1-4612-3466-1_16
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
D. Leivant
中科院分区：
文献类型：
--
作者：
D. Leivant
As a contribution to ongoing research on computing over general algebraic structures, we consider subrecurrence over free algebras. Since the natural sub-recursive classification of functions by recurrence-nesting depth fails to separate polynomial from exponential numeric functions, we define a subrecursive hierarchy {Tn}nwhich does, based on nesting depth of a newly definedtieredrecurrence.We show that, for algebras with at least one non-unary function, no non-trivial level of (at least one variant of) the hierarchy is finitely generated. This contrasts with the result of [Par68] about numeric subrecursion, and therefore testifies to a fundamental dissimilarity between numeric computing and general algebraic computing.One variant of tiered recurrence yieldsT2= the functions over free algebras A-representable in the simply typed ⋋calculus1⋋. This characterization is akin to the main result of [Zaiα]. We conclude that the class of functions over trees that are representable in1⋋is not finitely generated, corroborating a conjecture in [Zai90].
