Results for 'Recursive functions'

999 found
Order:
  1.  59
    Theory of Recursive Functions and Effective Computability.H. Rogers - 1987 - MIT Press.
  2.  25
    Ramsey's Theorem for Pairs and Provably Recursive Functions.Alexander Kreuzer & Ulrich Kohlenbach - 2009 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  3. Formal Systems and Recursive Functions.John N. Crossley & Michael A. E. Dummett (eds.) - 1965 - Amsterdam: North-Holland Pub. Co..
     
    Export citation  
     
    Bookmark  
  4. Recursive Functions and Metamathematics Problems of Completeness and Decidability, Gödel's Theorems.Roman Murawski - 1999
     
    Export citation  
     
    Bookmark  
  5.  7
    Some Hierarchies of Primitive Recursive Functions on Term Algebras.Klaus-Hilmar Sprenger - 1997 - Mathematical Logic Quarterly 43 (2):251-286.
  6.  26
    Unary Primitive Recursive Functions.Daniel E. Severin - 2008 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  6
    Factors of Functions, AC and Recursive Analogues.Wolfgang Degen - 2002 - 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 (3 more)  
     
    Export citation  
     
    Bookmark  
  8.  10
    Induction Rules, Reflection Principles, and Provably Recursive Functions.Lev D. Beklemishev - 1997 - 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 (10 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  9. Accessible Recursive Functions.Stanley S. Wainer - 1999 - 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 (11 more)  
     
    Export citation  
     
    Bookmark  
  10.  17
    Term Rewriting Theory for the Primitive Recursive Functions.E. A. Cichon & Andreas Weiermann - 1997 - 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 recursive functions to (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  11.  33
    An Exactification of the Monoid of Primitive Recursive Functions.Joachim Lambek & Philip Scott - 2005 - 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 (7 more)  
     
    Export citation  
     
    Bookmark  
  12.  24
    A Lift of a Theorem of Friedberg: A Banach-Mazur Functional That Coincides with No Α-Recursive Functional on the Class of Α-Recursive Functions.Robert A. di Paola - 1981 - 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 (8 more)  
     
    Export citation  
     
    Bookmark  
  13.  15
    Formal Systems and Recursive Functions[REVIEW]J. M. P. - 1965 - Review of Metaphysics 19 (1):161-162.
    This is a collection of papers read at an international logic colloquium held at Oxford in 1963. The first half contains articles on intuitionistic and modal logics, the propositional calculus, and languages with infinitely long expressions by such logicians as Kripke, Bull, Harrop, and Tait. The second part is primarily concerned with recursive functions and features a monograph by Crossley on constructive order types, as well as contributions by Goodstein, Schütte, and Wang, among others. Especially noteworthy is Kripke's (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  6
    Inhomogeneity of the P-s-Degrees of Recursive Functions.Asae Mochizuki & Juichi Shinoda - 2000 - 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.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  15.  22
    On Modal Logics of Partial Recursive Functions.Pavel Naumov - 2005 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  21
    Characterizing the Elementary Recursive Functions by a Fragment of Gödel's T.Arnold Beckmann & Andreas Weiermann - 2000 - 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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  17.  46
    Matt Fairtlough and Stanley S. Wainer. Hierarchies of Provably Recursive Functions. Handbook of Proof Theory, Edited by Samuel R. Buss, Studies in Logic and the Foundations of Mathematics, Vol. 137, Elsevier, Amsterdam Etc. 1998, Pp. 149–207. [REVIEW]Toshiyasu Arai - 2000 - Bulletin of Symbolic Logic 6 (4):466-467.
  18.  25
    On a Complexity-Based Way of Constructivizing the Recursive Functions.F. W. Kroon & W. A. Burkhard - 1990 - 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  
     
    Bookmark   1 citation  
  19.  9
    Plain Bases for Classes of Primitive Recursive Functions.Stefano Mazzanti - 2002 - 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.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  20.  20
    The Intrinsic Difficulty of Recursive Functions.F. W. Kroon - 1996 - 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  
     
    Bookmark  
  21.  8
    A Direct Method for Simulating Partial Recursive Functions by Diophantine Equations.Yuri Matiyasevich - 1994 - 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 (4 more)  
     
    Export citation  
     
    Bookmark  
  22. Expressing and Capturing the Primitive Recursive Functions.Peter Smith - unknown
    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 (...)
     
    Export citation  
     
    Bookmark  
  23.  19
    Robert W. Ritchie. Classes of Recursive Functions Based on Ackermann's Function. Pacific Journal of Mathematics, Vol. 15 , Pp. 1027–1044. [REVIEW]Paul Axt - 1966 - Journal of Symbolic Logic 31 (4):654-654.
  24.  17
    Julia Robinson. Recursive Functions of One Variable. Proceedings of the American Mathematical Society, Vol. 19 , Pp. 815–820. [REVIEW]Martin Davis - 1970 - Journal of Symbolic Logic 35 (3):476.
  25.  16
    Hisao Yamada. Real-Time Computation and Recursive Functions Not Real-Time Computable. IRE Transactions on Electronic Computers, Vol. EC-11 , Pp. 753–760. [REVIEW]Jiří Bečvář - 1966 - Journal of Symbolic Logic 31 (4):656-657.
  26.  16
    M. J. Cresswell. The Logic of Interrogatives. Formal Systems and Recursive Functions, Proceedings of the Eighth Logic Colloquium, Oxford, July 1963, Edited by J. N. Crossley and M. A. E. Dummett, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam1965, Pp. 8–11. [REVIEW]Gerold Stahl - 1966 - Journal of Symbolic Logic 31 (4):668-668.
  27.  14
    Saul A. Kripke. Semantical Analysis of Intuitionistic Logic I. Formal Systems and Recursive Functions, Proceedings of the Eighth Logic Colloquium, Oxford, July 1963, Edited by J. N. Crossley and M. A. E. Dummett, Series in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam1965, Pp. 92–130. [REVIEW]G. Kreisel - 1970 - Journal of Symbolic Logic 35 (2):330-332.
  28.  14
    W. W. Tait. Infinitely Long Terms of Transfinite Type. Formal Systems and Recursive Functions, Proceedings of the Eighth Logic Colloquium, Oxford, July 1963, Edited by J. N. Crossley and M. A. E. Dummett, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam 1965, Pp. 176–185. [REVIEW]E. G. K. LóPez-Escobar - 1975 - Journal of Symbolic Logic 40 (4):623-624.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  29.  13
    J. C. Shepherdson Und H. E. Sturgis. Computability of Recursive Functions. Journal of the Association for Computing Machinery, Bd. 10 , S. 217–255. [REVIEW]Günter Asser - 1967 - Journal of Symbolic Logic 32 (1):122-123.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  30.  13
    Kurt Schütte. Predicative Well-Orderings. Formal Systems and Recursive Functions, Proceedings of the Eighth Logic Colloquium, Oxford, July 1963, Edited by J. N. Crossley and M. A. E. Dummett, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam1965, Pp. 280–303. - Kurt Schütte. Eine Grenze Fúr Die Beweisbarkeit der Transfiniten Induktion in der Verzweigten Typenlogik. Archiv Für Mathematische Logik Und Grundlagenforschung, Vol. 7 , Pp. 45–60. [REVIEW]Charles Parsons - 1967 - Journal of Symbolic Logic 32 (2):284-285.
  31.  12
    A. Bertoni. Mathematical Methods of the Theory of Stochastic Automata. Mathematical Foundations of Computer Science, 3rd Symposium at Jadwisin Near Warsaw, June 17–22, 1974, Edited by A. Blikle, Lecture Notes in Computer Science, Vol. 28, Springer-Verlag, Berlin, Heidelberg, and New York, 1975, Pp. 9–22. - R. V. Freivald. Functions Computable in the Limit by Probabilistic Machines. Mathematical Foundations of Computer Science, 3rd Symposium at Jadwisin Near Warsaw, June 17–22, 1974, Edited by A. Blikle, Lecture Notes in Computer Science, Vol. 28, Springer-Verlag, Berlin, Heidelberg, and New York, 1975, Pp. 77–87. - B. Goetze and R. Klette. Some Properties of Limit Recursive Functions. Mathematical Foundations of Computer Science, 3rd Symposium at Jadwisin Near Warsaw, June 17–22, 1974, Edited by A. Blikle, Lecture Notes in Computer Science, Vol. 28, Springer-Verlag, Berlin, Heidelberg, and New York, 1975, Pp. 88–90. - Ole-Johan Dahl. An Approach to Correctness Proofs of Semicoroutines. [REVIEW]Steven S. Muchnick - 1977 - Journal of Symbolic Logic 42 (3):422-423.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  32.  12
    Jaakko Hintikka. Distributive Normal Forms in First-Order Logic. Formal Systems and Recursive Functions, Proceedings of the Eighth Logic Colloquium, Oxford, July 1963, Edited by J. N. Crossley and M. A. E. Dummett, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam1965, Pp. 48–91. - Jaakko Hintikka. Distributive Normal Forms and Deductive Interpolation. Zeitschrift Für Mathematische Logik Und Grundlagen der Mathematik, Vol. 10 , Pp. 185–191. [REVIEW]F. C. Oglesby - 1966 - Journal of Symbolic Logic 31 (2):267-268.
  33.  11
    Frederic B. Fitch. Recursive Functions in Basic Logic. The Journal of Symbolic Logic, Vol. 21 , Pp. 337–346.R. A. DiPaola - 1970 - Journal of Symbolic Logic 35 (1):152-153.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  34.  11
    Richard Montague. Set Theory and Higher-Order Logic. Formal Systems and Recursive Functions, Proceedings of the Eighth Logic Colloquium, Oxford, July 1963, Edited by J. N. Crossley and M. A. E. Dummett, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam1965, Pp. 131–148. [REVIEW]Richard Mansfield - 1975 - Journal of Symbolic Logic 40 (3):459.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  35.  10
    Lev D. Beklemishev. Induction Rules, Reflection Principles, and Provably Recursive Functions. Annals of Pure and Applied Logic, Vol. 85 , Pp. 193–242. [REVIEW]Volker Halbach - 2002 - Bulletin of Symbolic Logic 8 (2):302-303.
  36.  9
    Patrick C. Fischer. Theory of Provable Recursive Functions. Transactions of the American Mathematical Society, Vol. 117 , Pp. 494–520. [REVIEW]H. B. Enderton - 1967 - Journal of Symbolic Logic 32 (2):270.
  37.  9
    N. A. Šanin. On the Constructive Interpretation of Mathematical Judgments. English Translation of XXXI 255 by Elliott Mendelson. American Mathematical Society Translations, Ser. 2 Vol. 23 , Pp. 109–189. - A. A. Markov. On Constructive Functions. English Translation of XXXI 258 by Moshe Machover. American Mathematical Society Translations, Vol. 29 , Pp. 163–195. - S. C. Kleene. A Formal System of Intuitionistic Analysis. The Foundations of Intuitionistlc Mathematics Especially in Relation to Recursive Functions, by Stephen Cole Kleene and Richard Eugene Vesley, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam1965, Pp. 1–89. - S. C. Kleene. Various Notions of Realizability:The Foundations of Intuitionistlc Mathematics Especially in Relation to Recursive Functions, by Stephen Cole Kleene and Richard Eugene Vesley, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam1965, Pp. 90–132. - Richard E. Ve. [REVIEW]Georg Kreisel - 1966 - Journal of Symbolic Logic 31 (2):258-261.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  38.  9
    A. N. Prior. Existence in Leśniewski and in Russell. Formal Systems and Recursive Functions, Proceedings of the Eighth Logic Colloquium, Oxford, July 1963, Edited by J. N. Crossley and M. A. E. Dummett, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam1965, Pp. 149–155. [REVIEW]C. Lejewski - 1975 - Journal of Symbolic Logic 40 (3):458.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  39.  8
    Manuel Blum. A Machine-Independent Theory of the Complexity of Recursive Functions. Journal of the Association for Computing Machinery, Vol. 14 , Pp. 322–336. [REVIEW]Stephen A. Cook - 1969 - Journal of Symbolic Logic 34 (4):657-658.
  40.  18
    Some Classes of Recursive Functions.Andrzej Grzegorczyk - 1955 - Journal of Symbolic Logic 20 (1):71-72.
  41.  69
    General Recursive Functions of Natural Numbers.S. C. Kleene - 1937 - Journal of Symbolic Logic 2 (1):38-38.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  42. Syntactic Translations and Provably Recursive Functions.Daniel Leivant - 1985 - Journal of Symbolic Logic 50 (3):682-688.
  43.  6
    H. B. Enderton. On Provable Recursive Functions. Notre Dame Journal of Formal Logic, Vol. 9 No. 1 , Pp. 86–88.Hartley Rogers - 1973 - Journal of Symbolic Logic 38 (3):526-527.
  44.  10
    Recursive and Nonextendible Functions Over the Reals; Filter Foundation for Recursive Analysis.II.Iraj Kalantari & Lawrence Welch - 1999 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  45.  5
    J. S. Ullian. Splinters of Recursive Functions. The Journal of Symbolic Logic, Vol. 25 No. 1 , Pp. 33–38.Marian Boykan Pour-El - 1966 - Journal of Symbolic Logic 31 (1):138-139.
  46.  85
    On the Algebraic Structure of Primitive Recursive Functions.István Szalkai - 1985 - Mathematical Logic Quarterly 31 (35‐36):551-556.
  47.  23
    Effective Operations on Partial Recursive Functions.J. Myhill & J. C. Shepherdson - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (4):310-317.
  48.  4
    Louise Hay. On Creative Sets and Indices of Partial Recursive Functions. Transactions of the American Mathematical Society, Vol. 120 No. 2 , Pp. 359–367. - Louise Hay. Isomorphism Types of Index Sets of Partial Recursive Functions. Proceedings of the American Mathematical Society, Vol. 17 , Pp. 106–110. - Louise Hay. Index Sets of Finite Classes of Recursively Enumerable Sets. The Journal of Symbolic Logic, Vol. 34 , Pp. 39–44. [REVIEW]Forbes D. Lewis - 1974 - Journal of Symbolic Logic 39 (1):186-187.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  49.  8
    Effective Operations on Partial Recursive Functions.J. Myhill & J. C. Shepherdson - 1955 - Mathematical Logic Quarterly 1 (4):310-317.
  50.  19
    Computability of Recursive Functions.J. C. Shepherdson & H. E. Sturgis - 1967 - Journal of Symbolic Logic 32 (1):122-123.
    Direct download  
     
    Export citation  
     
    Bookmark   8 citations  
1 — 50 / 999