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: 90.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: 75.0
    No categories
     
    My bibliography  
     
    Export citation  
  3. H. Rogers (1987). Theory of Recursive Functions and Effective Computability. Mit Press.score: 75.0
  4. Klaus‐Hilmar Sprenger (1997). Some Hierarchies of Primitive Recursive Functions on Term Algebras. Mathematical Logic Quarterly 43 (2):251-286.score: 71.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: 66.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: 60.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: 60.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: 60.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. W. Degen (2002). Factors of Functions, AC and Recursive Analogues. Mathematical Logic Quarterly 48 (1):73-86.score: 60.0
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  10. Pavel Naumov (2005). On Modal Logics of Partial Recursive Functions. Studia Logica 81 (3):295 - 309.score: 58.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  
  11. Luis E. Sanchis (1992). Recursive Functionals. North-Holland.score: 58.0
    This work is a self-contained elementary exposition of the theory of recursive functionals, that also includes a number of advanced results.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  12. Martin Davis (ed.) (1965/2004). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions. Dover Publication.score: 54.0
    "A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers by (...)
    Direct download  
     
    My bibliography  
     
    Export citation  
  13. Manuel L. Campagnolo & Kerry Ojakian (2008). The Elementary Computable Functions Over the Real Numbers: Applying Two New Techniques. [REVIEW] Archive for Mathematical Logic 46 (7-8):593-627.score: 54.0
    The basic motivation behind this work is to tie together various computational complexity classes, whether over different domains such as the naturals or the reals, or whether defined in different manners, via function algebras (Real Recursive Functions) or via Turing Machines (Computable Analysis). We provide general tools for investigating these issues, using two techniques we call approximation and lifting. We use these methods to obtain two main theorems. First, we provide an alternative proof of the result from Campagnolo (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  14. 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: 52.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  
  15. F. W. Kroon & W. A. Burkhard (1990). On a Complexity-Based Way of Constructivizing the Recursive Functions. Studia Logica 49 (1):133 - 149.score: 51.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  
  16. Peter Smith, Expressing and Capturing the Primitive Recursive Functions.score: 51.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
    Translate to English
    |
     
    My bibliography  
     
    Export citation  
  17. Holger Petersen (1996). The Computation of Partial Recursive Word‐Functions Without Read Instructions. Mathematical Logic Quarterly 42 (1):312-318.score: 50.0
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  18. Michael Rathjen (1992). A Proof-Theoretic Characterization of the Primitive Recursive Set Functions. Journal of Symbolic Logic 57 (3):954-969.score: 48.0
    Let KP- be the theory resulting from Kripke-Platek set theory by restricting Foundation to Set Foundation. Let G: V → V (V:= universe of sets) be a ▵0-definable set function, i.e. there is a ▵0-formula φ(x, y) such that φ(x, G(x)) is true for all sets x, and $V \models \forall x \exists!y\varphi (x, y)$ . In this paper we shall verify (by elementary proof-theoretic methods) that the collection of set functions primitive recursive in G coincides with the (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  19. F. W. Kroon (1996). The Intrinsic Difficulty of Recursive Functions. Studia Logica 56 (3):427 - 454.score: 48.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  
  20. Ján Komara (2011). On Nested Simple Recursion. Archive for Mathematical Logic 50 (5-6):617-624.score: 48.0
    We give a novel proof that primitive recursive functions are closed under nested simple recursion. This new presentation is supplied with a detailed proof which can be easily formalized in small fragments of Peano Arithmetic.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  21. Qing Zhou (1996). Computable Real‐Valued Functions on Recursive Open and Closed Subsets of Euclidean Space. Mathematical Logic Quarterly 42 (1):379-409.score: 48.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  22. S. Mazzanti (2002). Plain Bases for Classes of Primitive Recursive Functions. Mathematical Logic Quarterly 48 (1):93-104.score: 47.0
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  23. George Boolos, John Burgess, Richard P. & C. Jeffrey (2007). Computability and Logic. Cambridge University Press.score: 45.0
    Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as Godel’s incompleteness theorems, but also a large number of optional topics, from Turing’s theory of computability to Ramsey’s theorem. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive (...), a traditional stumbling block for students on the way to the Godel incompleteness theorems. (shrink)
    Direct download  
     
    My bibliography  
     
    Export citation  
  24. Nigel Cutland (1980). Computability, an Introduction to Recursive Function Theory. Cambridge University Press.score: 45.0
    What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland (...)
    Direct download  
     
    My bibliography  
     
    Export citation  
  25. 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: 45.0
    History and Philosophy of Logic, Volume 33, Issue 2, Page 191, May 2012.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  26. Daniel Leivant (1985). Syntactic Translations and Provably Recursive Functions. Journal of Symbolic Logic 50 (3):682-688.score: 45.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  27. Peter Smith, Primitive Recursive Functions.score: 45.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
    Translate to English
    |
     
    My bibliography  
     
    Export citation  
  28. Hartley Rogers Jr (1958). Gödel Numberings of Partial Recursive Functions. Journal of Symbolic Logic 23 (3):331-341.score: 45.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  29. Mingzhong Cai (2012). Degrees of Relative Provability. Notre Dame Journal of Formal Logic 53 (4):479-489.score: 45.0
    There are many classical connections between the proof-theoretic strength of systems of arithmetic and the provable totality of recursive functions. In this paper we study the provability strength of the totality of recursive functions by investigating the degree structure induced by the relative provability order of recursive algorithms. We prove several results about this proof-theoretic degree structure using recursion-theoretic techniques such as diagonalization and the Recursion Theorem.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  30. C. H. Applebaum & J. C. E. Dekker (1970). Partial Recursive Functions and Ω-Functions. Journal of Symbolic Logic 35 (4):559-568.score: 45.0
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  31. Frederic B. Fitch (1956). Recursive Functions in Basic Logic. Journal of Symbolic Logic 21 (4):337-346.score: 45.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  32. 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: 45.0
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  33. 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: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  34. 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: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  35. R. M. Martin (1949). A Note on Nominalism and Recursive Functions. Journal of Symbolic Logic 14 (1):27-31.score: 45.0
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  36. 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: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  37. Cristian Calude (1982). Topological Size of Sets of Partial Recursive Functions. Mathematical Logic Quarterly 28 (27‐32):455-462.score: 45.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  38. J. P. Cleave (1963). A Hierarchy of Primitive Recursive Functions. Mathematical Logic Quarterly 9 (22):331-346.score: 45.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  39. Andrzej Mostowski (1950). Review: A. A. Markov, On the Representation of Recursive Functions. [REVIEW] Journal of Symbolic Logic 15 (1):66-66.score: 45.0
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  40. Rozsa Peter (1954). Review: A. Mostowski, A Lemma Concerning Recursive Functions and Its Applications. [REVIEW] Journal of Symbolic Logic 19 (4):299-300.score: 45.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: 45.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: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  43. J. S. Ullian (1960). Splinters of Recursive Functions. Journal of Symbolic Logic 25 (1):33-38.score: 45.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  44. Paul Axt (1959). Review: J. R. Shoenfield, The Class of Recursive Functions. [REVIEW] Journal of Symbolic Logic 24 (3):238-239.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  45. 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: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  46. Carl H. Smith (1988). A Note on Arbitrarily Complex Recursive Functions. Notre Dame Journal of Formal Logic 29 (2):198-207.score: 45.0
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  47. 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: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  48. Martin Davis (1964). Review: Hartley Rogers, Godel Numberings of Partial Recursive Functions. [REVIEW] Journal of Symbolic Logic 29 (3):146-146.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  49. 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: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  50. Rod Downey (2002). Roman Murawski, Recursive Functions and Metamathematics. Studia Logica 70 (2):297-299.score: 45.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
1 — 50 / 1000