Results for 'Recursive functions'

955 found
Order:
  1.  36
    Recursive Functions and Metamathematics: Problems of Completeness and Decidability, Gödel's Theorems.Rod J. L. Adams & Roman Murawski - 1999 - Dordrecht, Netherland: Springer Verlag.
    Traces the development of recursive functions from their origins in the late nineteenth century to the mid-1930s, with particular emphasis on the work and influence of Kurt Gödel.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  2.  17
    Recursive functionals.Luis E. Sanchis - 1992 - New York: North-Holland.
    This work is a self-contained elementary exposition of the theory of recursive functionals, that also includes a number of advanced results.
    Direct download  
     
    Export citation  
     
    Bookmark  
  3. 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 (9 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  19
    Recursive Functions and Intuitionistic Number Theory.David Nelson - 1947 - Journal of Symbolic Logic 12 (3):93-94.
  5.  99
    Computability, an introduction to recursive function theory.Nigel Cutland - 1980 - New York: Cambridge University Press.
    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 (...)
  6.  33
    Recursive functions and existentially closed structures.Emil Jeřábek - 2019 - Journal of Mathematical Logic 20 (1):2050002.
    The purpose of this paper is to clarify the relationship between various conditions implying essential undecidability: our main result is that there exists a theory T in which all partially recursive functions are representable, yet T does not interpret Robinson’s theory R. To this end, we borrow tools from model theory — specifically, we investigate model-theoretic properties of the model completion of the empty theory in a language with function symbols. We obtain a certain characterization of ∃∀ theories (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  7. Theory of recursive functions and effective computability.Hartley Rogers - 1987 - Cambridge: MIT Press.
  8.  14
    Recursive Functionals and Quantifiers of Finite Types II.S. C. Kleene - 1971 - Journal of Symbolic Logic 36 (1):146-146.
  9.  10
    Recursive Functions of One Variable.Julia Robinson - 1970 - Journal of Symbolic Logic 35 (3):476-476.
  10.  20
    Non recursive functionals.Richard Bird - 1975 - Mathematical Logic Quarterly 21 (1):41-46.
  11.  17
    Synthesising recursive functions with side effects.Ria Follett - 1980 - Artificial Intelligence 13 (3):175-200.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  27
    Recursive Functions and Intuitionistic Mathematics.S. C. Kleene - 1953 - Journal of Symbolic Logic 18 (2):181-182.
  13.  50
    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 (5 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  14.  22
    General Recursive Functions.Julia Robinson - 1951 - Journal of Symbolic Logic 16 (4):280-280.
  15.  46
    Partial recursive functions and ω-functions.C. H. Applebaum & J. C. E. Dekker - 1970 - Journal of Symbolic Logic 35 (4):559-568.
  16. (1 other version)Formal Systems and Recursive Functions.Michael Dummett & J. N. Crossley (eds.) - 1963 - Amsterdam,: North Holland.
  17.  42
    Recursive functions in basic logic.Frederic B. Fitch - 1956 - Journal of Symbolic Logic 21 (4):337-346.
  18.  24
    Recursive Function Theory.John Myhill - 1968 - Journal of Symbolic Logic 33 (4):619-620.
    Direct download  
     
    Export citation  
     
    Bookmark  
  19.  8
    Primitive Recursive Functions. II.Raphael M. Robinson - 1957 - Journal of Symbolic Logic 22 (4):375-376.
  20.  27
    (1 other version)A Hierarchy of Primitive Recursive Functions.J. P. Cleave - 1963 - Mathematical Logic Quarterly 9 (22):331-346.
  21.  90
    (1 other version)Gödel numberings of partial recursive functions.Hartley Rogers - 1958 - Journal of Symbolic Logic 23 (3):331-341.
  22.  42
    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  
  23. Roman Murawski, recursive functions and metamathematics: Problems of completeness and decidability.E. Mendelson - 2000 - Philosophia Mathematica 8 (3):345-346.
     
    Export citation  
     
    Bookmark  
  24.  9
    A note on recursive functions.S. C. Kleene - 1936 - Journal of Symbolic Logic 1 (3):119-119.
  25. Primitive recursive functions.Peter Smith - unknown
    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.
     
    Export citation  
     
    Bookmark  
  26.  50
    Some Classes of Recursive Functions.Andrzej Grzegorczyk - 1955 - Journal of Symbolic Logic 20 (1):71-72.
  27.  19
    (1 other version)Embedding Properties of Total Recursive Functions.W. Maier, W. Menzel & V. Sperschneider - 1982 - Mathematical Logic Quarterly 28 (33‐38):565-574.
  28.  10
    Primitive Recursive Functions.Raphael M. Robinson - 1948 - Journal of Symbolic Logic 13 (2):113-114.
  29.  77
    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 (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  30.  23
    Constructively nonpartial recursive functions.Bruce M. Horowitz - 1980 - Notre Dame Journal of Formal Logic 21 (2):273-276.
  31.  21
    General Recursive Functions in the Number-Theoretic Formal System.Sh^|^Ocirc Maehara & Ji - 1957 - Annals of the Japan Association for Philosophy of Science 1 (2):119-130.
  32.  22
    Selection functions for recursive functionals.Thomas J. Grilliot - 1969 - Notre Dame Journal of Formal Logic 10 (3):225-234.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  33.  24
    (1 other version)Effective operations on partial recursive functions.J. Myhill & J. C. Shepherdson - 1955 - Mathematical Logic Quarterly 1 (4):310-317.
  34.  28
    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  
     
    Export citation  
     
    Bookmark  
  35.  37
    Effective Operations and Partial Recursive Functionals.G. Kriesel, D. Lacombe, J. Shoenfield, G. Kreisel & J. R. Shoenfield - 1966 - Journal of Symbolic Logic 31 (2):261-262.
    Direct download  
     
    Export citation  
     
    Bookmark  
  36.  22
    (1 other version)Classes of One‐Argument Recursive Functions.Nadejda V. Georgieva - 1976 - Mathematical Logic Quarterly 22 (1):127-130.
  37.  45
    Hierarchies of Primitive Recursive Functions.Charles Parsons - 1968 - Mathematical Logic Quarterly 14 (21-24):357-376.
  38. S. C. Kleene. General recursive functions of natural numbers. Mathematische Annalen, Bd. 112 (1935–1936), S. 727–742.S. C. Kleene - 1937 - Journal of Symbolic Logic 2 (1):38-38.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   35 citations  
  39.  41
    Provably recursive functions of constructive and relatively constructive theories.Morteza Moniri - 2010 - Archive for Mathematical Logic 49 (3):291-300.
    In this paper we prove conservation theorems for theories of classical first-order arithmetic over their intuitionistic version. We also prove generalized conservation results for intuitionistic theories when certain weak forms of the principle of excluded middle are added to them. Members of two families of subsystems of Heyting arithmetic and Buss-Harnik’s theories of intuitionistic bounded arithmetic are the intuitionistic theories we consider. For the first group, we use a method described by Leivant based on the negative translation combined with a (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  40.  56
    A foundation for real recursive function theory.José Félix Costa, Bruno Loff & Jerzy Mycka - 2009 - Annals of Pure and Applied Logic 160 (3):255-288.
    The class of recursive functions over the reals, denoted by , was introduced by Cristopher Moore in his seminal paper written in 1995. Since then many subsequent investigations brought new results: the class was put in relation with the class of functions generated by the General Purpose Analogue Computer of Claude Shannon; classical digital computation was embedded in several ways into the new model of computation; restrictions of were proved to represent different classes of recursive (...), e.g., recursive, primitive recursive and elementary functions, and structures such as the Ritchie and the Grzergorczyk hierarchies.The class of real recursive functions was then stratified in a natural way, and and the analytic hierarchy were recently recognised as two faces of the same mathematical concept.In this new article, we bring a strong foundational support to the Real Recursive Function Theory, rooted in Mathematical Analysis, in a way that the reader can easily recognise both its intrinsic mathematical beauty and its extreme simplicity. The new paradigm is now robust and smooth enough to be taught. To achieve such a result some concepts had to change and some new results were added. (shrink)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  41.  15
    General Recursive Functions in the Number-Theoretic Formal System.Shôji Maehara - 1957 - Annals of the Japan Association for Philosophy of Science 1 (2):119-130.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  42.  21
    Some Hierarchies of Primitive Recursive Functions on Term Algebras.Klaus-Hilmar Sprenger - 1997 - Mathematical Logic Quarterly 43 (2):251-286.
  43.  46
    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   7 citations  
  44.  56
    Computability of Recursive Functions.J. C. Shepherdson & H. E. Sturgis - 1967 - Journal of Symbolic Logic 32 (1):122-123.
    Direct download  
     
    Export citation  
     
    Bookmark   15 citations  
  45.  46
    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 (4 more)  
     
    Export citation  
     
    Bookmark  
  46.  51
    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 (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  47.  20
    Roman Murawski, Recursive Functions and Metamathematics. [REVIEW]Roman Murawski - 2002 - Studia Logica 70 (2):297-299.
    Direct download  
     
    Export citation  
     
    Bookmark   8 citations  
  48.  51
    An early history of recursive functions and computability from Gödel to Turing.I. Grattan-Guinness - 2012 - History and Philosophy of Logic 33 (2):191 - 191.
    History and Philosophy of Logic, Volume 33, Issue 2, Page 191, May 2012.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  49.  28
    On provable recursive functions.H. B. Enderton - 1968 - Notre Dame Journal of Formal Logic 9 (1):86-88.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  50.  13
    The Foundations of Intuitionistic Mathematics: Especially in Relation to Recursive Functions.Stephen Cole Kleene & Richard Eugene Vesley - 1965 - Amsterdam: North-Holland Pub. Co.. Edited by Richard Eugene Vesley.
1 — 50 / 955