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

1000+ found
Order:
  1.  7
    H. Rogers (1987). Theory of Recursive Functions and Effective Computability. MIT Press.
  2.  9
    Alexander Kreuzer & Ulrich Kohlenbach (2009). Ramsey's Theorem for Pairs and Provably Recursive Functions. Notre Dame Journal of Formal Logic 50 (4):427-444.
    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)  
     
    Export citation  
     
    My bibliography   1 citation  
  3. John N. Crossley & Michael A. E. Dummett (eds.) (1965). Formal Systems and Recursive Functions. Amsterdam, North-Holland Pub. Co..
    No categories
     
    Export citation  
     
    My bibliography  
  4. Roman Murawski (1999). Recursive Functions and Metamathematics Problems of Completeness and Decidability, Gödel's Theorems.
     
    Export citation  
     
    My bibliography  
  5.  4
    Klaus‐Hilmar Sprenger (1997). Some Hierarchies of Primitive Recursive Functions on Term Algebras. Mathematical Logic Quarterly 43 (2):251-286.
  6.  10
    Daniel E. Severin (2008). Unary Primitive Recursive Functions. Journal of Symbolic Logic 73 (4):1122-1138.
    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)  
     
    Export citation  
     
    My bibliography   1 citation  
  7.  2
    W. Degen (2002). Factors of Functions, AC and Recursive Analogues. Mathematical Logic Quarterly 48 (1):73-86.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  8. Stanley S. Wainer (1999). Accessible Recursive Functions. Bulletin of Symbolic Logic 5 (3):367-388.
    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)  
     
    Export citation  
     
    My bibliography  
  9.  6
    Lev D. Beklemishev (1997). Induction Rules, Reflection Principles, and Provably Recursive Functions. Annals of Pure and Applied Logic 85 (3):193-242.
    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)  
     
    Export citation  
     
    My bibliography   7 citations  
  10.  7
    E. A. Cichon & Andreas Weiermann (1997). Term Rewriting Theory for the Primitive Recursive Functions. Annals of Pure and Applied Logic 83 (3):199-223.
    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 (...) functions to primitive recursive functions. (shrink)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  11.  10
    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.
    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)  
     
    Export citation  
     
    My bibliography  
  12.  28
    Joachim Lambek & Philip Scott (2005). An Exactification of the Monoid of Primitive Recursive Functions. Studia Logica 81 (1):1 - 18.
    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 (5 more)  
     
    Export citation  
     
    My bibliography  
  13.  8
    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.
    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)  
     
    Export citation  
     
    My bibliography  
  14.  1
    A. Mochizuki & J. Shinoda (2000). Inhomogeneity of the P-s-Degrees of Recursive Functions. Mathematical Logic Quarterly 46 (3):385-392.
    The structure of the p-s-degrees of recursive functions is shown to be inhomogeneous. There are two p-s-degrees a and b above 0 such that [0, a] is distributive and [0, b] is nondistributive. Moreover, we will investigate how the number of values of each function reflects on its degree.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  15.  14
    Pavel Naumov (2005). On Modal Logics of Partial Recursive Functions. Studia Logica 81 (3):295 - 309.
    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 (5 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  16.  8
    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.
    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)  
     
    Export citation  
     
    My bibliography   1 citation  
  17.  15
    F. W. Kroon & W. A. Burkhard (1990). On a Complexity-Based Way of Constructivizing the Recursive Functions. Studia Logica 49 (1):133 - 149.
    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)  
     
    Export citation  
     
    My bibliography   1 citation  
  18.  16
    F. W. Kroon (1996). The Intrinsic Difficulty of Recursive Functions. Studia Logica 56 (3):427 - 454.
    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)  
     
    Export citation  
     
    My bibliography  
  19.  5
    S. Mazzanti (2002). Plain Bases for Classes of Primitive Recursive Functions. Mathematical Logic Quarterly 48 (1):93-104.
    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 (4 more)  
     
    Export citation  
     
    My bibliography  
  20.  5
    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.
    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)  
     
    Export citation  
     
    My bibliography  
  21. Peter Smith, Expressing and Capturing the Primitive Recursive Functions.
    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
     
    Export citation  
     
    My bibliography  
  22.  74
    István Szalkai (1985). On the Algebraic Structure of Primitive Recursive Functions. Mathematical Logic Quarterly 31 (35‐36):551-556.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  23. Daniel Leivant (1985). Syntactic Translations and Provably Recursive Functions. Journal of Symbolic Logic 50 (3):682-688.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  24.  2
    Andrzej Grzegorczyk (1955). Some Classes of Recursive Functions. Journal of Symbolic Logic 20 (1):71-72.
    Direct download  
     
    Export citation  
     
    My bibliography   21 citations  
  25.  17
    R. Moll & A. R. Meyer (1974). Honest Bounds for Complexity Classes of Recursive Functions. Journal of Symbolic Logic 39 (1):127-138.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  26.  3
    Iraj Kalantari & Lawrence Welch (1999). Recursive and Nonextendible Functions Over the Reals; Filter Foundation for Recursive Analysis.II. Annals of Pure and Applied Logic 98 (1-3):87-110.
    In this paper we continue our work of Kalantari and Welch . There we introduced machinery to produce a point-free approach to points and functions on topological spaces and found conditions for both which lend themselves to effectivization. While we studied recursive points in that paper, here, we present two useful classes of recursive functions on topological spaces, apply them to the reals, and find precise accounting for the nature of the properties of some examples that (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  27.  4
    Paul Axt (1961). Note on the 3-Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 7 (7-10):97-98.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  28.  4
    J. P. Cleave (1963). A Hierarchy of Primitive Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 9 (22):331-346.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  29.  4
    Nadejda V. Georgieva (1976). Classes of One-Argument Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 22 (1):127-130.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  30.  4
    Keith Harrow (1979). Equivalence of Some Hierarchies of Primitive Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 25 (25-29):411-418.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  31.  4
    Hilbert Levitz, Warren Nichols & Robert F. Smith (1991). A Macro Program for the Primitive Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 37 (8):121-124.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  32.  4
    F. D. Lewis (1971). Classes of Recursive Functions and Their Index Sets. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 17 (1):291-294.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  33.  4
    Albert R. Meyer & Dennis M. Ritchie (1972). A Classification of the Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 18 (4-6):71-82.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  34.  4
    J. Myhill & J. C. Shepherdson (1955). Effective Operations on Partial Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (4):310-317.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  35.  4
    Charles Parsons (1968). Hierarchies of Primitive Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 14 (21-24):357-376.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  36.  2
    J. C. Shepherdson & H. E. Sturgis (1967). Computability of Recursive Functions. Journal of Symbolic Logic 32 (1):122-123.
    Direct download  
     
    Export citation  
     
    My bibliography   5 citations  
  37.  13
    Hartley Rogers Jr (1958). Gödel Numberings of Partial Recursive Functions. Journal of Symbolic Logic 23 (3):331-341.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  38.  4
    Cristian Calude (1982). Topological Size of Sets of Partial Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 28 (27-32):455-462.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  39.  4
    W. Maier, W. Menzel & V. Sperschneider (1982). Embedding Properties of Total Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 28 (33-38):565-574.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  40.  4
    Gregory A. Riccardi (1982). The Independence of Control Structures in Programmable Numberings of the Partial Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 28 (20-21):285-296.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  41.  4
    Gisela Schäfer (1985). A Note on Conjectures of Calude About the Topological Size of Sets of Partial Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 31 (14-18):279-280.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  42.  4
    István Szalkai (1985). On the Algebraic Structure of Primitive Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 31 (35-36):551-556.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  43.  5
    Stanley S. Wainer (1998). Hierarchies of Provably Recursive Functions. In Samuel R. Buss (ed.), Bulletin of Symbolic Logic. Elsevier 149.
  44.  2
    Joachim Lambek & Philip Scott (2005). An Exactification of the Monoid of Primitive Recursive Functions. Studia Logica 81 (1):1-18.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  45.  2
    Pavel Naumov (2005). On Modal Logics of Partial Recursive Functions. Studia Logica 81 (3):295-309.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  46. Julia Robinson (1970). Recursive Functions of One Variable. Journal of Symbolic Logic 35 (3):476-476.
    Direct download  
     
    Export citation  
     
    My bibliography   4 citations  
  47.  5
    John W. Berry (1974). N-Ary Almost Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 20 (34-36):551-559.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  48.  2
    J. Myhill & J. C. Shepherdson (1955). Effective Operations on Partial Recursive Functions. Mathematical Logic Quarterly 1 (4):310-317.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  49. Gunter Asser (1967). Review: J. C. Shepherdson, H. E. Sturgis, Computability of Recursive Functions. [REVIEW] Journal of Symbolic Logic 32 (1):122-123.
     
    Export citation  
     
    My bibliography  
  50.  4
    R. M. Martin (1949). A Note on Nominalism and Recursive Functions. Journal of Symbolic Logic 14 (1):27-31.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   3 citations  
1 — 50 / 1000