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

1000+ 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
    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
    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
    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. 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
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  22. 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  
  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. 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  
  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. 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  
  30. 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  
  31. 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  
  32. 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  
  33. 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  
  34. 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  
  35. 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  
  36. 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  
  37. 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  
  38. 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  
  39. 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  
  40. 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  
  41. 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  
  42. 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  
  43. 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  
  44. 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
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  45. 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  
  46. Martin Davis (1964). Review: Hartley Rogers, Godel Numberings of Partial Recursive Functions. [REVIEW] Journal of Symbolic Logic 29 (3):146-146.score: 150.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  47. 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  
  48. Rod Downey (2002). Roman Murawski, Recursive Functions and Metamathematics. Studia Logica 70 (2):297-299.score: 150.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  49. Erik Ellentuck (1967). Review: J. Barback, Recursive Functions and Regressive Isols. [REVIEW] Journal of Symbolic Logic 32 (2):269-270.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  50. H. B. Enderton (1967). Review: Patrick C. Fischer, Theory of Provable Recursive Functions. [REVIEW] Journal of Symbolic Logic 32 (2):270-270.score: 150.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
1 — 50 / 1000