Skip to main content
10 events
when toggle format what by license comment
Sep 25, 2023 at 14:29 comment added Jii @JoelDavidHamkins Fixed, thank you.
Sep 25, 2023 at 14:29 history edited Jii CC BY-SA 4.0
deleted 2 characters in body
Sep 25, 2023 at 11:48 comment added Joel David Hamkins You seem to have a typo in the tau iteration scheme, as once you reduce from n+1 to n+1 instead of n.
Sep 25, 2023 at 10:42 answer added Stanisław Ambroszkiewicz timeline score: 2
Aug 2, 2022 at 17:41 comment added Jii @FedorPakhomov Yep, the existence itself is clear. We could, for example, use the fast-growing hierarchy and define mentioned subrecursive hierarchy as closures over the PR and a chosen $f_\alpha$ for $\alpha<\epsilon_0$. However, I'm interested if we can define a hierarchy without any notion to ordinals, in (kind of) more "constructive" way just using the higher order recursion schema, but I have not been able to locate any references (only those around lambda calculus that employ different tools).
Aug 2, 2022 at 15:25 comment added Fedor Pakhomov However, the other direction, i.e. assignment of ordinals to $T$-terms was studied. See for example this paper by Andreas Weiermann cambridge.org/core/journals/journal-of-symbolic-logic/article/…
Aug 2, 2022 at 15:23 comment added Fedor Pakhomov Of course, there are two well-known descriptions of $\mathsf{PA}$-provable total computable functions on naturals as 1. functions given by a system $T$ term of the type $\mathbb{N}\to\mathbb{N}$ and 2. functions that are elementary-recursive relative to some $F_\alpha$, where $\alpha<\varepsilon_0$. The combination of this two results immediately implies that each $F_\alpha$, $\alpha<\varepsilon_0$ could be written as a system $T$ term. I don't know whether this terms have been already explicitly by anyone before, although wouldn't be surprised if it would be the case.
Aug 2, 2022 at 15:02 comment added Jii @FedorPakhomov Yes, I'm targeting "pure number-theoretical" setup here, thus the lambda abstraction is somewhat out of scope. The core idea is to reach a hierarchy like that of Grzegorczyk's within the class PR, but within the class of functions provable total in PA. I remember reading about the combinators earlier, I need to revisit that. Thanks for the pointer.
Aug 2, 2022 at 14:50 comment added Fedor Pakhomov This is a bit beyond my area of expertise. But it seems to me that you just need to take system $T$ as the language of description of higher-order functionals. There are at least two ways how one could define system $T$: 1. using $\lambda$-abstraction, 2. using combinators. From your question it seems to me that you want to have primitive functions (rather than $\lambda$-terms). Hence you should check the formulation of system $T$ with combinators. Unfortunately, I don't know what is a good reference about that.
Aug 2, 2022 at 9:07 history asked Jii CC BY-SA 4.0