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.  19
    Recursive Functions and Intuitionistic Number Theory.David Nelson - 1947 - Journal of Symbolic Logic 12 (3):93-94.
  4.  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  
  5. Theory of recursive functions and effective computability.Hartley Rogers - 1987 - Cambridge: MIT Press.
  6.  10
    Recursive Functions of One Variable.Julia Robinson - 1970 - Journal of Symbolic Logic 35 (3):476-476.
  7.  14
    Recursive Functionals and Quantifiers of Finite Types II.S. C. Kleene - 1971 - Journal of Symbolic Logic 36 (1):146-146.
  8.  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  
  9.  27
    Recursive Functions and Intuitionistic Mathematics.S. C. Kleene - 1953 - Journal of Symbolic Logic 18 (2):181-182.
  10.  22
    General Recursive Functions.Julia Robinson - 1951 - Journal of Symbolic Logic 16 (4):280-280.
  11. 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  
  12.  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 (...)
  13. (1 other version)Formal Systems and Recursive Functions.Michael Dummett & J. N. Crossley (eds.) - 1963 - Amsterdam,: North Holland.
  14.  24
    Recursive Function Theory.John Myhill - 1968 - Journal of Symbolic Logic 33 (4):619-620.
    Direct download  
     
    Export citation  
     
    Bookmark  
  15.  8
    Primitive Recursive Functions. II.Raphael M. Robinson - 1957 - Journal of Symbolic Logic 22 (4):375-376.
  16.  10
    Primitive Recursive Functions.Raphael M. Robinson - 1948 - Journal of Symbolic Logic 13 (2):113-114.
  17.  9
    A note on recursive functions.S. C. Kleene - 1936 - Journal of Symbolic Logic 1 (3):119-119.
  18. Roman Murawski, recursive functions and metamathematics: Problems of completeness and decidability.E. Mendelson - 2000 - Philosophia Mathematica 8 (3):345-346.
     
    Export citation  
     
    Bookmark  
  19.  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  
  20.  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.
  21. 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  
  22.  50
    Some Classes of Recursive Functions.Andrzej Grzegorczyk - 1955 - Journal of Symbolic Logic 20 (1):71-72.
  23.  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.
  24.  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  
  25.  45
    Hierarchies of Primitive Recursive Functions.Charles Parsons - 1968 - Mathematical Logic Quarterly 14 (21-24):357-376.
  26.  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  
  27.  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  
  28.  22
    (1 other version)Classes of One‐Argument Recursive Functions.Nadejda V. Georgieva - 1976 - Mathematical Logic Quarterly 22 (1):127-130.
  29.  24
    (1 other version)Effective operations on partial recursive functions.J. Myhill & J. C. Shepherdson - 1955 - Mathematical Logic Quarterly 1 (4):310-317.
  30.  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  
  31.  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  
  32. 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  
  33.  46
    Partial recursive functions and ω-functions.C. H. Applebaum & J. C. E. Dekker - 1970 - Journal of Symbolic Logic 35 (4):559-568.
  34.  21
    Some Hierarchies of Primitive Recursive Functions on Term Algebras.Klaus-Hilmar Sprenger - 1997 - Mathematical Logic Quarterly 43 (2):251-286.
  35.  20
    Non recursive functionals.Richard Bird - 1975 - Mathematical Logic Quarterly 21 (1):41-46.
  36.  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  
  37.  43
    Recursive functions in basic logic.Frederic B. Fitch - 1956 - Journal of Symbolic Logic 21 (4):337-346.
  38.  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  
  39.  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.
  40.  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  
  41.  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  
  42.  53
    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  
  43.  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  
  44.  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  
  45.  20
    Roman Murawski, Recursive Functions and Metamathematics. [REVIEW]Roman Murawski - 2002 - Studia Logica 70 (2):297-299.
    Direct download  
     
    Export citation  
     
    Bookmark   8 citations  
  46.  28
    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  
  47.  13
    A Lemma Concerning Recursive Functions and Its Applications.A. Mostowski - 1954 - Journal of Symbolic Logic 19 (4):299-300.
  48.  45
    (1 other version)Hierarchies of Provably Recursive Functions.Stanley S. Wainer - 1998 - In Samuel R. Buss (ed.), Handbook of proof theory. New York: Elsevier. pp. 149.
  49.  19
    (1 other version)A Classification of the Recursive Functions.Albert R. Meyer & Dennis M. Ritchie - 1972 - Mathematical Logic Quarterly 18 (4‐6):71-82.
  50.  69
    Origins of Recursive Function Theory.Stephen C. Kleene & Martin Davis - 1990 - Journal of Symbolic Logic 55 (1):348-350.
    Direct download  
     
    Export citation  
     
    Bookmark   15 citations  
1 — 50 / 955