Search results for 'Recursive functions' (try it on Scholar)

996 found
Sort by:
  1. Alexander Kreuzer & Ulrich Kohlenbach (2009). Ramsey's Theorem for Pairs and Provably Recursive Functions. Notre Dame Journal of Formal Logic 50 (4):427-444.score: 240.0
    This paper addresses the strength of Ramsey's theorem for pairs ($RT^2_2$) over a weak base theory from the perspective of 'proof mining'. Let $RT^{2-}_2$ denote Ramsey's theorem for pairs where the coloring is given by an explicit term involving only numeric variables. We add this principle to a weak base theory that includes weak König's Lemma and a substantial amount of $\Sigma^0_1$-induction (enough to prove the totality of all primitive recursive functions but not of all primitive recursive (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  2. John N. Crossley & Michael A. E. Dummett (eds.) (1965). Formal Systems and Recursive Functions. Amsterdam, North-Holland Pub. Co..score: 210.0
    No categories
     
    My bibliography  
     
    Export citation  
  3. H. Rogers (1987). Theory of Recursive Functions and Effective Computability. Mit Press.score: 210.0
  4. Klaus‐Hilmar Sprenger (1997). Some Hierarchies of Primitive Recursive Functions on Term Algebras. Mathematical Logic Quarterly 43 (2):251-286.score: 202.0
    We compare two different Grzegorczyk hierarchies {Hnσ}n≥0 and {Lnσ}n≥1 on term algebras, which grow according to the height and length of terms, respectively. The solution of almost all inclusion problems among the Grzegorczyk classes and the recursion number classes Rnσ and Snσ on term algebras shows {Hnσ}n≥0 to generalize Weihrauch's Grzegorczyk hierarchy on words {Enk}n≥0 to arbitrary term algebras. However, by regarding terms as words, {Lnσ}n≥1 turns out to be computationally equivalent to Weihrauch's hierarchy {Enσ}n≥0 on the whole. Especially, L2σ} (...)
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Daniel E. Severin (2008). Unary Primitive Recursive Functions. Journal of Symbolic Logic 73 (4):1122-1138.score: 192.0
    In 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.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  6. Joachim Lambek & Philip Scott (2005). An Exactification of the Monoid of Primitive Recursive Functions. Studia Logica 81 (1):1 - 18.score: 180.0
    We study the monoid of primitive recursive functions and investigate a onestep construction of a kind of exact completion, which resembles that of the familiar category of modest sets, except that the partial equivalence relations which serve as objects are recursively enumerable. As usual, these constructions involve the splitting of symmetric idempotents.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  7. Robert A. Di Paola (1981). A Lift of a Theorem of Friedberg: A Banach-Mazur Functional That Coincides with No Α-Recursive Functional on the Class of Α-Recursive Functions. Journal of Symbolic Logic 46 (2):216 - 232.score: 180.0
    R. M. Friedberg demonstrated the existence of a recursive functional that agrees with no Banach-Mazur functional on the class of recursive functions. In this paper Friedberg's result is generalized to both α-recursive functionals and weak α-recursive functionals for all admissible ordinals α such that $\lambda , where α * is the Σ 1 -projectum of α and λ is the Σ 2 -cofinality of α. The theorem is also established for the metarecursive case, α = (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  8. Stanley S. Wainer (1999). Accessible Recursive Functions. Bulletin of Symbolic Logic 5 (3):367-388.score: 180.0
    The class of all recursive functions fails to possess a natural hierarchical structure, generated predicatively from "within". On the other hand, many (proof-theoretically significant) sub-recursive classes do. This paper attempts to measure the limit of predicative generation in this context, by classifying and characterizing those (predictably terminating) recursive functions which can be successively defined according to an autonomy condition of the form: allow recursions only over well-orderings which have already been "coded" at previous levels. The (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  9. Pavel Naumov (2005). On Modal Logics of Partial Recursive Functions. Studia Logica 81 (3):295 - 309.score: 176.0
    The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and non-deterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  10. W. Degen (2002). Factors of Functions, AC and Recursive Analogues. Mathematical Logic Quarterly 48 (1):73-86.score: 168.0
    We investigate certain statements about factors of unary functions which have connections with weak forms of the axiom of choice. We discuss more extensively the fine structure of Howard and Rubin's Form 314 from [4]. Some of our set-theoretic results have also interesting recursive versions.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  11. Arnold Beckmann & Andreas Weiermann (2000). Characterizing the Elementary Recursive Functions by a Fragment of Gödel's T. Archive for Mathematical Logic 39 (7):475-491.score: 164.0
    Let T be Gödel's system of primitive recursive functionals of finite type in a combinatory logic formulation. Let $T^{\star}$ be the subsystem of T in which the iterator and recursor constants are permitted only when immediately applied to type 0 arguments. By a Howard-Schütte-style argument the $T^{\star}$ -derivation lengths are classified in terms of an iterated exponential function. As a consequence a constructive strong normalization proof for $T^{\star}$ is obtained. Another consequence is that every $T^{\star}$ -representable number-theoretic function is (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  12. F. W. Kroon & W. A. Burkhard (1990). On a Complexity-Based Way of Constructivizing the Recursive Functions. Studia Logica 49 (1):133 - 149.score: 162.0
    Let g E(m, n)=o mean that n is the Gödel-number of the shortest derivation from E of an equation of the form (m)=k. Hao Wang suggests that the condition for general recursiveness mn(g E(m, n)=o) can be proved constructively if one can find a speedfunction s s, with s(m) bounding the number of steps for getting a value of (m), such that mn s(m) s.t. g E(m, n)=o. This idea, he thinks, yields a constructivist notion of an effectively computable function, (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  13. Peter Smith, Expressing and Capturing the Primitive Recursive Functions.score: 162.0
    The last Episode wasn’t about logic or formal theories at all: it was about common-or-garden arithmetic and the informal notion of computability. We noted that addition can be defined in terms of repeated applications of the successor function. Multiplication can be defined in terms of repeated applications of addition. The exponential and factorial functions can be defined, in different ways, in terms of repeated applications of multiplication. There’s already a pattern emerging here! The main task in the last Episode (...)
    No categories
     
    My bibliography  
     
    Export citation  
  14. F. W. Kroon (1996). The Intrinsic Difficulty of Recursive Functions. Studia Logica 56 (3):427 - 454.score: 156.0
    This paper deals with a philosophical question that arises within the theory of computational complexity: how to understand the notion of INTRINSIC complexity or difficulty, as opposed to notions of difficulty that depend on the particular computational model used. The paper uses ideas from Blum's abstract approach to complexity theory to develop an extensional approach to this question. Among other things, it shows how such an approach gives detailed confirmation of the view that subrecursive hierarchies tend to rank functions (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  15. S. Mazzanti (2002). Plain Bases for Classes of Primitive Recursive Functions. Mathematical Logic Quarterly 48 (1):93-104.score: 154.0
    Abasisforaset C of functions on natural numbers is a set F of functions such that C is the closure with respect to substitution of the projection functions and the functions in F. This paper introduces three new bases, comprehending only common functions, for the Grzegorczyk classes ℰn with n ≥ 3. Such results are then applied in order to show that ℰn+1 = Kn for n ≥ 2, where {Kn}n∈ℕ is the Axt hierarchy.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  16. Daniel Leivant (1985). Syntactic Translations and Provably Recursive Functions. Journal of Symbolic Logic 50 (3):682-688.score: 150.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  17. I. Grattan-Guinness (2012). An Early History of Recursive Functions and Computability From Gödel to Turing. History and Philosophy of Logic 33 (2):191 - 191.score: 150.0
    History and Philosophy of Logic, Volume 33, Issue 2, Page 191, May 2012.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  18. Hartley Rogers Jr (1958). Gödel Numberings of Partial Recursive Functions. Journal of Symbolic Logic 23 (3):331-341.score: 150.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  19. Peter Smith, Primitive Recursive Functions.score: 150.0
    In our preamble, it might be helpful this time to give a story about where we are going, rather than (as in previous episodes) review again where we’ve been. So, at the risk of spoiling the excitement, here’s what’s going to happen in this and the following three Episodes.
    No categories
     
    My bibliography  
     
    Export citation  
  20. C. H. Applebaum & J. C. E. Dekker (1970). Partial Recursive Functions and Ω-Functions. Journal of Symbolic Logic 35 (4):559-568.score: 150.0
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  21. Gunter Asser (1967). Review: J. C. Shepherdson, H. E. Sturgis, Computability of Recursive Functions. [REVIEW] Journal of Symbolic Logic 32 (1):122-123.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  22. Robert A. Di Paola (1981). A Lift of a Theorem of Friedberg: A Banach-Mazur Functional That Coincides with No Α-Recursive Functional on the Class of Α-Recursive Functions. Journal of Symbolic Logic 46 (2):216-232.score: 150.0
    R. M. Friedberg demonstrated the existence of a recursive functional that agrees with no Banach-Mazur functional on the class of recursive functions. In this paper Friedberg's result is generalized to both α-recursive functionals and weak α-recursive functionals for all admissible ordinals α such that $\lambda , where α * is the Σ 1 -projectum of α and λ is the Σ 2 -cofinality of α. The theorem is also established for the metarecursive case, α = (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  23. Volker Halbach (2002). Review: Lev D. Beklemishev, Induction Rules, Reflection Principles, and Provably Recursive Functions. [REVIEW] Bulletin of Symbolic Logic 8 (2):302-303.score: 150.0
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  24. Frederic B. Fitch (1956). Recursive Functions in Basic Logic. Journal of Symbolic Logic 21 (4):337-346.score: 150.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  25. Paul Axt (1997). Ritchie Robert W.. Classes of Recursive Functions Based on Ackermann's Function. Pacific Journal of Mathematics, Vol. 15 (1965), Pp. 1027–1044. [REVIEW] Journal of Symbolic Logic 31 (4):654-654.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  26. Martin Davis (1968). Review: John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. [REVIEW] Journal of Symbolic Logic 33 (1):117-117.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  27. R. M. Martin (1949). A Note on Nominalism and Recursive Functions. Journal of Symbolic Logic 14 (1):27-31.score: 150.0
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  28. J. S. Ullian (1960). Splinters of Recursive Functions. Journal of Symbolic Logic 25 (1):33-38.score: 150.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  29. Paul Axt (1959). Review: J. R. Shoenfield, The Class of Recursive Functions. [REVIEW] Journal of Symbolic Logic 24 (3):238-239.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  30. Cristian Calude (1982). Topological Size of Sets of Partial Recursive Functions. Mathematical Logic Quarterly 28 (27‐32):455-462.score: 150.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  31. J. P. Cleave (1963). A Hierarchy of Primitive Recursive Functions. Mathematical Logic Quarterly 9 (22):331-346.score: 150.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  32. J. C. E. Dekker (1957). Review: J. Myhill, J. C. Shepherdson, Effective Operations on Partial Recursive Functions. [REVIEW] Journal of Symbolic Logic 22 (3):303-303.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  33. R. A. DiPaola (1970). Review: Frederic B. Fitch, Recursive Functions in Basic Logic. [REVIEW] Journal of Symbolic Logic 35 (1):152-153.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  34. H. B. Enderton (1968). On Provable Recursive Functions. Notre Dame Journal of Formal Logic 9 (1):86-88.score: 150.0
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  35. C. F. Kent (1971). Review: Charles Parsons, Hierarchies of Primitive Recursive Functions. [REVIEW] Journal of Symbolic Logic 36 (3):538-539.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  36. Yuri Matiyasevich (1994). A Direct Method for Simulating Partial Recursive Functions by Diophantine Equations. Annals of Pure and Applied Logic 67 (1-3):325-348.score: 150.0
    A new proof is given of the celebrated theorem of M. Davis, H. Putnam and J. Robinson concerning exponential Diophantine representation of recursively enumerable predicates. The proof goes by induction on the defining scheme of a partial recursive function.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  37. Andrzej Mostowski (1950). Review: A. A. Markov, On the Representation of Recursive Functions. [REVIEW] Journal of Symbolic Logic 15 (1):66-66.score: 150.0
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  38. Rozsa Peter (1954). Review: A. Mostowski, A Lemma Concerning Recursive Functions and Its Applications. [REVIEW] Journal of Symbolic Logic 19 (4):299-300.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  39. Rozsa Peter (1957). Review: Raphael M. Robinson, Primitive Recursive Functions. II. [REVIEW] Journal of Symbolic Logic 22 (4):375-376.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  40. Rozsa Peter (1937). Review: S. C. Kleene, General Recursive Functions of Natural Numbers. [REVIEW] Journal of Symbolic Logic 2 (1):38-38.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  41. Marian Boykan Pour-El (1966). Review: J. S. Ullian, Splinters of Recursive Functions. [REVIEW] Journal of Symbolic Logic 31 (1):138-139.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  42. J. R. Shoenfield (1962). Review: Shoji Maehara, General Recursive Functions in the Number-Theoretic Formal System. [REVIEW] Journal of Symbolic Logic 27 (1):90-90.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  43. Gerold Stahl (1997). Cresswell MJ. The Logic of Interrogatives. Formal Systems and Recursive Functions, Proceedings of the Eighth Logic Colloquium, Oxford, July 1963, Edited by Crossley JN and Dummett MAE, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam 1965, Pp. 8–11. [REVIEW] Journal of Symbolic Logic 31 (4):668-668.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  44. Paul Axt (1966). Review: Robert W. Ritchie, Classes of Recursive Functions Based on Ackermann's Function. [REVIEW] Journal of Symbolic Logic 31 (4):654-654.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  45. Jiri Becvar (1966). Review: Hisao Yamada, Real-Time Computation and Recursive Functions Not Real-Time Computable. [REVIEW] Journal of Symbolic Logic 31 (4):656-657.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  46. Lev D. Beklemishev (1997). Induction Rules, Reflection Principles, and Provably Recursive Functions. Annals of Pure and Applied Logic 85 (3):193-242.score: 150.0
    A well-known result states that, over basic Kalmar elementary arithmetic EA, the induction schema for ∑n formulas is equivalent to the uniform reflection principle for ∑n + 1 formulas . We show that fragments of arithmetic axiomatized by various forms of induction rules admit a precise axiomatization in terms of reflection principles as well. Thus, the closure of EA under the induction rule for ∑n formulas is equivalent to ω times iterated ∑n reflection principle. Moreover, for k < ω, k (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  47. Jiří Bečvář (1997). Yamada Hisao. Real-Time Computation and Recursive Functions Not Real-Time Computable. IRE Transactions on Electronic Computers, Vol. EC-11 (1962), Pp. 753–760. [REVIEW] Journal of Symbolic Logic 31 (4):656-657.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  48. Carl H. Smith (1988). A Note on Arbitrarily Complex Recursive Functions. Notre Dame Journal of Formal Logic 29 (2):198-207.score: 150.0
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  49. E. A. Cichon & Andreas Weiermann (1997). Term Rewriting Theory for the Primitive Recursive Functions. Annals of Pure and Applied Logic 83 (3):199-223.score: 150.0
    The termination of rewrite systems for parameter recursion, simple nested recursion and unnested multiple recursion is shown by using monotone interpretations both on the ordinals below the first primitive recursively closed ordinal and on the natural numbers. We show that the resulting derivation lengths are primitive recursive. As a corollary we obtain transparent and illuminating proofs of the facts that the schemata of parameter recursion, simple nested recursion and unnested multiple recursion lead from primitive recursive functions to (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  50. Stephen A. Cook (1969). Review: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions. [REVIEW] Journal of Symbolic Logic 34 (4):657-658.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
1 — 50 / 996