Log in

Relevant bibliographies by topics / Primitive recursive / Journal articles

To see the other types of publications on this topic, follow the link: Primitive recursive.

Journal articles on the topic 'Primitive recursive'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Primitive recursive.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Severin, Daniel E. "Unary primitive recursive functions." Journal of Symbolic Logic 73, no. 4 (2008): 1122–38. http://dx.doi.org/10.2178/jsl/1230396909.

Full text

Abstract:

AbstractIn this article, we study some new characterizations of primitive recursive functions based on restricted forms of primitive recursion, improving the pioneering work of R. M. Robinson and M. D. Gladstone. We reduce certain recursion schemes (mixed/pure iteration without parameters) and we characterize one-argument primitive recursive functions as the closure under substitution and iteration of certain optimal sets.

APA, Harvard, Vancouver, ISO, and other styles

2

Urzyczyn, Pawel. "Primitive Recursion with Existential Types1." Fundamenta Informaticae 19, no. 1-2 (1993): 201–22. http://dx.doi.org/10.3233/fi-1993-191-209.

Full text

Abstract:

We consider computability over abstract structures with help of primitive recursive definitions (an appropriate modification of Gödel’s system T). Unlike the standard approach, we do not assume any fixed representation of integers, but instead we allow primitive recursion to be polymorphic, so that iteration is performed with help of counters viewed as objects of an abstract type Int of arbitrary (hidden) implementation. This approach involves the use of existential quantification in types, following the ideas of Mitchell and Plotkin. We show that the halting problem over finite interpretations is primitive recursive for each program involving primitive recursive definitions. Conversely, each primitive recursive set of interpretations is defined by the termination property of some program.

APA, Harvard, Vancouver, ISO, and other styles

3

Kalimullin, I. Sh, and A. G. Melnikov. "Punctual Categoricity Relative to a Computable Oracle." Lobachevskii Journal of Mathematics 42, no. 4 (2021): 735–42. http://dx.doi.org/10.1134/s1995080221040107.

Full text

Abstract:

Abstract We are studying the punctual structures, i.e., the primitive recursive structures on the whole set of integers. The punctual categoricity relative to a computable oracle $$f$$ means that between any two punctual copies of a structure there is an isomorphism which togeteher with its inverse can be derived via primitive recursive schemes augmented with $$f$$. We will prove that the punctual categoricity relative to a computable oracle can hold only for finitely generated or locally finite structures. We will show that the punctual categoricity of finitely generated structures is exhaused by the computable oracles with primitive recursive graph. We also present an example of locally finite structure where the punctual categoricity is provided by a primitive recursively bounded computable oracle.

APA, Harvard, Vancouver, ISO, and other styles

4

Chen, Qingliang, Kaile Su, and Xizhong Zheng. "Primitive recursive real numbers." MLQ 53, no. 4-5 (2007): 365–80. http://dx.doi.org/10.1002/malq.200710005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Colson, Loïc. "About primitive recursive algorithms." Theoretical Computer Science 83, no. 1 (1991): 57–69. http://dx.doi.org/10.1016/0304-3975(91)90039-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

KOHLENBACH, ULRICH. "A UNIFORM QUANTITATIVE FORM OF SEQUENTIAL WEAK COMPACTNESS AND BAILLON'S NONLINEAR ERGODIC THEOREM." Communications in Contemporary Mathematics 14, no. 01 (2012): 1250006. http://dx.doi.org/10.1142/s021919971250006x.

Full text

Abstract:

We apply proof-theoretic techniques of "proof mining" to obtain an effective uniform rate of metastability in the sense of Tao for Baillon's famous nonlinear ergodic theorem in Hilbert space. In fact, we analyze a proof due to Brézis and Browder of Baillon's theorem relative to the use of weak sequential compactness. Using previous results due to the author we show the existence of a bar recursive functional Ω* (using only lowest type bar recursion B0, 1) providing a uniform quantitative version of weak compactness. Primitive recursively in this functional (and hence in T0 + B0, 1) we then construct an explicit bound φ on for the metastable version of Baillon's theorem. From the type level of φ and another result of the author it follows that φ is primitive recursive in the extended sense of Gödel's T. In a subsequent paper also Ω* will be explicitly constructed leading to the refined complexity estimate φ ∈ T4.

APA, Harvard, Vancouver, ISO, and other styles

7

Kalimullin, I. Sh, and R. Miller. "Primitive recursive fields and categoricity." Algebra i logika 58, no. 1 (2019): 132–38. http://dx.doi.org/10.33048/alglog.2019.58.108.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Damnjanovic, Zlatan. "Strictly primitive recursive realizability, I." Journal of Symbolic Logic 59, no. 4 (1994): 1210–27. http://dx.doi.org/10.2307/2275700.

Full text

Abstract:

AbstractA realizability notion that employs only primitive recursive functions is defined, and, relative to it, the soundness of the fragment of Heyting Arithmetic (HA) in which induction is restricted to formulae is proved. A dual concept of falsifiability is proposed and an analogous soundness result is established for a further restricted fragment of HA.

APA, Harvard, Vancouver, ISO, and other styles

9

Kalimullin, I. Sh, and R. Miller. "Primitive Recursive Fields and Categoricity." Algebra and Logic 58, no. 1 (2019): 95–99. http://dx.doi.org/10.1007/s10469-019-09527-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Hasan, Sartaj Ul, Daniel Panario, and Qiang Wang. "Nonlinear vectorial primitive recursive sequences." Cryptography and Communications 10, no. 6 (2017): 1075–90. http://dx.doi.org/10.1007/s12095-017-0265-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Meinke, Karl. "A recursive second order initial algebra specification of primitive recursion." Acta Informatica 31, no. 4 (1994): 329–40. http://dx.doi.org/10.1007/bf01178510.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Leivant, Daniel. "Finitism, imperative programs and primitive recursion." Journal of Logic and Computation 31, no. 1 (2021): 179–92. http://dx.doi.org/10.1093/logcom/exaa076.

Full text

Abstract:

Abstract Following the Crisis of Foundations Hilbert proposed to consider a finitistic form of arithmetic as mathematics’ safe core. This approach to finitism has often admitted primitive recursive function definitions as obviously finitistic, but some have advocated the inclusion of additional variants of recurrence, while others argued that, to the contrary, primitive recursion exceeds finitism. In a landmark essay, William Tait contested the finitistic nature of these extensions, due to their impredicativity, and advocated identifying finitism with primitive recursive arithmetic, a stance often referred to as Tait’s Thesis. However, a problem with Tait’s argument is that the recurrence schema has itself impredicative and non-finitistic facets, starting with an explicit reference to the functions being defined, which are after all infinite objects. It is therefore desirable to buttress Tait’s Thesis on grounds that avoid altogether any trace of concrete infinities or impredicativity. We propose here to do just that, building on the generic framework of [ 13]. We provide further evidence for Tait’s Thesis by outlining a proof of a purely finitistic version of Parsons’ theorem, whose intuitive gist is that finitistic reasoning is equivalent to finitistic computing.

APA, Harvard, Vancouver, ISO, and other styles

13

Paolini, Luca, Mauro Piccolo, and Luca Roversi. "A class of Recursive Permutations which is Primitive Recursive complete." Theoretical Computer Science 813 (April 2020): 218–33. http://dx.doi.org/10.1016/j.tcs.2019.11.029.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Konovalov, A. Yu. "Arithmetical realizability and primitive recursive realizability." Moscow University Mathematics Bulletin 71, no. 4 (2016): 166–69. http://dx.doi.org/10.3103/s0027132216040069.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

David, R. "Decidability results for primitive recursive algorithms." Theoretical Computer Science 300, no. 1-3 (2003): 477–504. http://dx.doi.org/10.1016/s0304-3975(02)00732-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Kościelski, Antoni, and Leszek Pacholski. "Makanin's algorithm is not primitive recursive." Theoretical Computer Science 191, no. 1-2 (1998): 145–56. http://dx.doi.org/10.1016/s0304-3975(96)00321-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

KÜNZI, URS-MARTIN. "Logic Programs for Primitive Recursive Sets." Journal of Logic and Computation 3, no. 4 (1993): 401–15. http://dx.doi.org/10.1093/logcom/3.4.401.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Jacobsson, Carl, and Viggo Stoltenberg-Hansen. "Poincaré-Betti Series are Primitive Recursive." Journal of the London Mathematical Society s2-31, no. 1 (1985): 1–9. http://dx.doi.org/10.1112/jlms/s2-31.1.1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Simmons, H. "The Ackermann functions are not optimal, but by how much?" Journal of Symbolic Logic 75, no. 1 (2010): 289–313. http://dx.doi.org/10.2178/jsl/1264433922.

Full text

Abstract:

AbstractBy taking a closer look at the construction of an Ackermann function we see that between any primitive recursive degree and its Ackermann modification there is a dense chain of primitive recursive degrees.

APA, Harvard, Vancouver, ISO, and other styles

20

Damnjanovic, Zlatan. "Strictly Primitive Recursive Realizability, II. Completeness with Respect to Iterated Reflection and a Primitive Recursive $\omega$-Rule." Notre Dame Journal of Formal Logic 39, no. 3 (1998): 363–88. http://dx.doi.org/10.1305/ndjfl/1039182252.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Weiermann, Andreas. "How is it that infinitary methods can be applied to finitary mathematics? Gödel's T: a case study." Journal of Symbolic Logic 63, no. 4 (1998): 1348–70. http://dx.doi.org/10.2307/2586654.

Full text

Abstract:

AbstractInspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Gödel's system T of primitive recursive functionals of finite types by constructing an ε0-recursive function []0: T → ω so that a reduces to b implies [a]0 > [b]0. The construction of [ ]0 is based on a careful analysis of the Howard-Schütte treatment of Gödel's T and utilizes the collapsing function ψ: ε0 → ω which has been developed by the author for a local predicativity style proof-theoretic analysis of PA. The construction of [ ]0 is also crucially based on ideas developed in the 1995 paper “A proof of strongly uniform termination for Gödel's T by the method of local predicativity” by the author. The results on complexity bounds for the fragments of T which are obtained in this paper strengthen considerably the results of the 1995 paper.Indeed, for given n let Tn be the subsystem of T in which the recursors have type level less than or equal to n + 2. (By definition, case distinction functionals for every type are also contained in Tn.) As a corollary of the main theorem of this paper we obtain (reobtain?) optimal bounds for the Tn-derivation lengths in terms of ω+2-descent recursive functions. The derivation lengths of type one functionals from Tn (hence also their computational complexities) are classified optimally in terms of <ωn+2 -descent recursive functions.In particular we obtain (reobtain?) that the derivation lengths function of a type one functional a ∈ T0 is primitive recursive, thus any type one functional a in T0 defines a primitive recursive function. Similarly we also obtain (reobtain?) a full classification of T1 in terms of multiple recursion.As proof-theoretic corollaries we reobtain the classification of the IΣn+1-provably recursive functions. Taking advantage from our finitistic and constructive treatment of the terms of Gödel's T we reobtain additionally (without employing continuous cut elimination techniques) that PRA + PRWO(ε0) ⊢ Π20 − Refl(PA) and PRA + PRWO(ωn+2) ⊢ Π20 − Refl(IΣn+1), hence PRA + PRWO(ε0) ⊢ Con(PA) and PRA + PRWO(ωn+2) ⊢ Con(IΣn+1).For programmatic reasons we outline in the introduction a vision of how to apply a certain type of infinitary methods to questions of finitary mathematics and recursion theory. We also indicate some connections between ordinals, term rewriting, recursion theory and computational complexity.

APA, Harvard, Vancouver, ISO, and other styles

22

Andary, Philippe, Bruno Patrou, and Pierre Valarcher. "A Representation Theorem for Primitive Recursive Algorithms." Fundamenta Informaticae 107, no. 4 (2011): 313–30. http://dx.doi.org/10.3233/fi-2011-405.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Georgiev, Ivan. "Continued fractions of primitive recursive real numbers." Mathematical Logic Quarterly 61, no. 4-5 (2015): 288–306. http://dx.doi.org/10.1002/malq.201400013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Frittaion, Emanuele. "Completeness of the primitive recursive $$\omega $$-rule." Archive for Mathematical Logic 59, no. 5-6 (2020): 715–31. http://dx.doi.org/10.1007/s00153-020-00716-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Paolini, Luca, Mauro Piccolo, and Luca Roversi. "A Class of Reversible Primitive Recursive Functions." Electronic Notes in Theoretical Computer Science 322 (April 2016): 227–42. http://dx.doi.org/10.1016/j.entcs.2016.03.016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Grigorieff, Serge. "Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))." Journal of Symbolic Logic 55, no. 1 (1990): 260–76. http://dx.doi.org/10.2307/2274966.

Full text

Abstract:

This paper is a contribution to the following natural problem in complexity theory:(*) Is there a complexity theory for isomorphism types of recursive countable relational structures? I.e. given a recursive relational structure ℛ over the set N of nonnegative integers, is there a nontrivial lower bound for the time-space complexity of recursive structures isomorphic (resp. recursively isomorphic) to ℛ?For unary recursive relations R, the answer is trivially negative: either R is finite or coinfinite or 〈N, R〉 is recursively isomorphic to 〈N, {x ϵ N: x is even}〉.The general problem for relations with arity 2 (or greater) is open.Related to this problem, a classical result (going back to S. C. Kleene [4], 1955) states that every recursive ordinal is in fact primitive recursive.In [3] Patrick Dehornoy, using methods relevant to computer science, improves this result, showing that every recursive ordinal can be represented by a recursive total ordering over N which has linear deterministic time complexity relative to the binary representation of integers. As he notices, his proof applies to every recursive total order type α such that the isomorphism type of α is not changed if points are replaced by arbitrary finite nonempty subsets of consecutive points.In this paper we extend Dehornoy's result to all recursive total orderings over N and get minimal complexity for both time and space simultaneously.

APA, Harvard, Vancouver, ISO, and other styles

27

JARDEN, MOSHE, and ALEXANDRA SHLAPENTOKH. "DECIDABLE ALGEBRAIC FIELDS." Journal of Symbolic Logic 82, no. 2 (2017): 474–88. http://dx.doi.org/10.1017/jsl.2017.10.

Full text

Abstract:

AbstractWe discuss the connection between decidability of a theory of a large algebraic extensions of ${\Bbb Q}$ and the recursiveness of the field as a subset of a fixed algebraic closure. In particular, we prove that if an algebraic extension K of ${\Bbb Q}$ has a decidable existential theory, then within any fixed algebraic closure $\widetilde{\Bbb Q}$ of ${\Bbb Q}$, the field K must be conjugate over ${\Bbb Q}$ to a field which is recursive as a subset of the algebraic closure. We also show that for each positive integer e there are infinitely many e-tuples $\sigma \in {\text{Gal}}\left( {\Bbb Q} \right)^e $ such that the field $\widetilde{\Bbb Q}\left( \sigma \right)$ is primitive recursive in $\widetilde{\Bbb Q}$ and its elementary theory is primitive recursively decidable. Moreover, $\widetilde{\Bbb Q}\left( \sigma \right)$ is PAC and ${\text{Gal}}\left( {\widetilde{\Bbb Q}\left( \sigma \right)} \right)$ is isomorphic to the free profinite group on e generators.

APA, Harvard, Vancouver, ISO, and other styles

28

David, René. "On the asymptotic behaviour of primitive recursive algorithms." Theoretical Computer Science 266, no. 1-2 (2001): 159–93. http://dx.doi.org/10.1016/s0304-3975(00)00165-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Zaslavsky, I. D. "On some generalizations of the primitive recursive arithmetic." Theoretical Computer Science 322, no. 1 (2004): 221–30. http://dx.doi.org/10.1016/j.tcs.2004.03.067.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Alaev, P. E. "Categoricity for Primitive Recursive and Polynomial Boolean Algebras." Algebra and Logic 57, no. 4 (2018): 251–74. http://dx.doi.org/10.1007/s10469-018-9498-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Cichon, E. A., and A. Weiermann. "Term rewriting theory for the primitive recursive functions." Annals of Pure and Applied Logic 83, no. 3 (1997): 199–223. http://dx.doi.org/10.1016/s0168-0072(96)00015-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Valarcher, P. "A complete characterization of primitive recursive intensional behaviours." RAIRO - Theoretical Informatics and Applications 42, no. 1 (2008): 69–82. http://dx.doi.org/10.1051/ita:2007053.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Shelah, Saharon. "Primitive recursive bounds for van der Waerden numbers." Journal of the American Mathematical Society 1, no. 3 (1988): 683. http://dx.doi.org/10.1090/s0894-0347-1988-0929498-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Mazzanti, Stefano. "Plain Bases for Classes of Primitive Recursive Functions." MLQ 48, no. 1 (2002): 93–104. http://dx.doi.org/10.1002/1521-3870(200201)48:1<93::aid-malq93>3.0.co;2-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Szalkai, István. "On the Algebraic Structure of Primitive Recursive Functions." Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 31, no. 35-36 (1985): 551–56. http://dx.doi.org/10.1002/malq.19850313503.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Schwartz, Daniel G. "A Free-Variable Theory of Primitive Recursive Arithmetic." Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 33, no. 2 (1987): 147–57. http://dx.doi.org/10.1002/malq.19870330210.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Levitz, Hilbert, Warren Nichols, and Robert F. Smith. "A Macro Program for the Primitive Recursive Functions." Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 37, no. 8 (1991): 121–24. http://dx.doi.org/10.1002/malq.19910370803.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

SEMIGRODSKIKH, A. P. "On Closed Classes of Primitive Recursive Functions, II." Multiple-Valued Logic 8, no. 2 (2002): 183–91. http://dx.doi.org/10.1080/10236620215292.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Deutsch, M., and M. Luban. "The primitive function for slit-height desmearing in SAXS." Journal of Applied Crystallography 20, no. 3 (1987): 179–81. http://dx.doi.org/10.1107/s0021889887086874.

Full text

Abstract:

The recursive method of Schmidt & Fedorov [J. Appl. Cryst. (1978). 11, 411–416] allows for calculation of the correction function g(t) for slit-height smearing in terms of the slit transmission function f(t). In this method, if the primitive function g(t) = g 0(t) is known for the interval 0 ≤ t ≤ t 0, then g(t) = gn (t) can be calculated recursively, for the intervals n ½ t 0 ≤ t ≤ (n + 1)½ t 0. A general method is presented for calculating g 0(t) in powers of t. To illustrate the utility of our method, three numerical examples are examined, indicating rapid convergence to a level of accuracy of 1 in 106.

APA, Harvard, Vancouver, ISO, and other styles

40

Leivant, Daniel, and Jean-Yves Marion. "Primitive recursion in the abstract." Mathematical Structures in Computer Science 30, no. 1 (2020): 33–43. http://dx.doi.org/10.1017/s0960129519000112.

Full text

Abstract:

AbstractRecurrence can be used as a function definition schema for any nontrivial free algebra, yielding the same computational complexity in all cases. We show that primitive-recursive computing is in fact independent of free algebras altogether, and can be characterized by a generic programming principle, namely the control of iteration by the depletion of finite components of the underlying structure.

APA, Harvard, Vancouver, ISO, and other styles

41

Riis, Søren. "Bootstrapping the primitive recursive functions by only 27 colors." Discrete Mathematics 169, no. 1-3 (1997): 269–72. http://dx.doi.org/10.1016/s0012-365x(97)87041-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Matos, Armando B. "The efficiency of primitive recursive functions: A programmer's view." Theoretical Computer Science 594 (August 2015): 65–81. http://dx.doi.org/10.1016/j.tcs.2015.04.022.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Sprenger, Klaus-Hilmar. "Some Hierarchies of Primitive Recursive Functions on Term Algebras." Mathematical Logic Quarterly 43, no. 2 (1997): 251–86. http://dx.doi.org/10.1002/malq.19970430208.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Goerdt, Andreas. "Characterizing complexity classes by higher type primitive recursive definitions." Theoretical Computer Science 100, no. 1 (1992): 45–66. http://dx.doi.org/10.1016/0304-3975(92)90363-k.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

López-Escobar, E. G. K. "König's lemma, the ω-Rule and primitive recursive arithmetic". Archiv für Mathematische Logik und Grundlagenforschung 25, № 1 (1985): 67–74. http://dx.doi.org/10.1007/bf02007557.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Lambek, Joachim, and Philip Scott. "An Exactification of the Monoid of Primitive Recursive Functions." Studia Logica 81, no. 1 (2005): 1–18. http://dx.doi.org/10.1007/s11225-005-2765-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Isles, David. "First-Order Reasoning and Primitive Recursive Natural Number Notations." Studia Logica 96, no. 1 (2010): 49–64. http://dx.doi.org/10.1007/s11225-010-9272-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Fouché, W. L., L. M. Pretorius, and C. J. Swanepoel. "Ramsey degrees of bipartite graphs: A primitive recursive proof." Discrete Mathematics 293, no. 1-3 (2005): 111–19. http://dx.doi.org/10.1016/j.disc.2004.08.035.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

DANNER, NORMAN, and DANIEL LEIVANT. "Stratified polymorphism and primitive recursion." Mathematical Structures in Computer Science 9, no. 4 (1999): 507–22. http://dx.doi.org/10.1017/s0960129599002868.

Full text

Abstract:

Natural restrictions on the syntax of the second-order (i.e., polymorphic) lambda calculus are of interest for programming language theory. One of the authors showed in Leivant (1991) that when type abstraction in that calculus is stratified into levels, the definable numeric functions are precisely the super-elementary functions (level [Escr ]4 in the Grzegorczyk Hierarchy). We define here a second-order lambda calculus in which type abstraction is stratified to levels up to ωω, an ordinal that permits highly uniform (and finite) type inference rules. Referring to this system, we show that the numeric functions definable in the calculus using ranks < ω[lscr ] are precisely Grzegorczyk's class [Escr ][lscr ]+3 ([lscr ] [ges ] 1). This generalizes Leivant (1991), where this is proved for [lscr ] = 1. Thus, the numeric functions definable in our calculus are precisely the primitive recursive functions.

APA, Harvard, Vancouver, ISO, and other styles

50

Kotlarski, Henryk. "An addition to Rosser's theorem." Journal of Symbolic Logic 61, no. 1 (1996): 285–92. http://dx.doi.org/10.2307/2275611.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!