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

1000+ found
Sort by:
  1. Nigel Cutland (1980). Computability, an Introduction to Recursive Function Theory. Cambridge University Press.score: 65.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). (...)
    Direct download  
     
    My bibliography  
     
    Export citation  
  2. H. R. Strong (1970). Construction of Models for Algebraically Generalized Recursive Function Theory. Journal of Symbolic Logic 35 (3):401-409.score: 60.0
    The Uniformly Reflexive Structure was introduced by E. G. Wagner who showed that the theory of such structures generalized much of recursive function theory. In this paper Uniformly Reflexive Structures are constructed as factor algebras of Free nonassociative algebras. Wagner's question about the existence of a model with no computable splinter ("successor set") is answered in the affirmative by the construction of a model whose only computable sets are the finite sets and their complements. Finally, for each countable (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  3. Klaus‐Hilmar Sprenger (1997). Some Hierarchies of Primitive Recursive Functions on Term Algebras. Mathematical Logic Quarterly 43 (2):251-286.score: 51.0
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  4. 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: 48.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 functionals). (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Holger Petersen (1996). The Computation of Partial Recursive Word‐Functions Without Read Instructions. Mathematical Logic Quarterly 42 (1):312-318.score: 48.0
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. R. L. Goodstein (1953). A Problem in Recursive Function Theory. Journal of Symbolic Logic 18 (3):225-232.score: 45.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  7. Stewart Shapiro (1990). Review: Stephen C. Kleene, Origins of Recursive Function Theory; Martin Davis, Why Godel Didn't Have Church's Thesis; Stephen C. Kleene, Reflections on Church's Thesis. [REVIEW] Journal of Symbolic Logic 55 (1):348-350.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  8. Bruno Kopp (2012). A Simple Hypothesis of Executive Function. Frontiers in Human Neuroscience 6.score: 45.0
    Executive function is traditionally conceptualized as a set of abilities required to guide behavior toward goals. Here, an integrated theoretical framework for executive function is developed which has its roots in the notion of hierarchical mental models. Further following Duncan (2010a,b), executive function is construed as a hierarchical recursive system of test-operation-test-exit units (Miller, Galanter, and Pribram, 1960). Importantly, it is shown that this framework can be used to model the main regional prefrontal syndromes, which are (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  9. J. W. Addison (2004). Tarski's Theory of Definability: Common Themes in Descriptive Set Theory, Recursive Function Theory, Classical Pure Logic, and Finite-Universe Logic. Annals of Pure and Applied Logic 126 (1-3):77-92.score: 45.0
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  10. J. P. Cleave (1974). Review: Webb Miller, Recursive Function Theory and Numerical Analysis. [REVIEW] Journal of Symbolic Logic 39 (2):346-346.score: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  11. Martin Davis (1997). Minsky ML. Size and Structure of Universal Turing Machines Using Tag Systems. Recursive Function Theory, Proceedings of Symposia in Pure Mathematics, Vol. 5, American Mathematical Society, Providence 1962, Pp. 229–238. [REVIEW] Journal of Symbolic Logic 31 (4):655-655.score: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  12. H. B. Enderton (1987). Review: Nigel Cutland, Computability. An Introduction to Recursive Function Theory. [REVIEW] Journal of Symbolic Logic 52 (1):292-293.score: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  13. Gustav Hensel (1966). Review: H. B. Enderton, Hierarchies in Recursive Function Theory. [REVIEW] Journal of Symbolic Logic 31 (2):262-263.score: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  14. Julia Robinson (1972). Review: Martin Davis, Application of Recursive Function Theory to Number Theory. [REVIEW] Journal of Symbolic Logic 37 (3):602-602.score: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  15. Heinrich Rolletschek (1983). Closure Properties of Almost-Finiteness Classes in Recursive Function Theory. Journal of Symbolic Logic 48 (3):756-763.score: 45.0
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  16. Joseph S. Ullian (1975). Review: Ann Yasuhara, Recursive Function Theory and Logic. [REVIEW] Journal of Symbolic Logic 40 (4):619-620.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  17. Paul Young (1972). Review: Manuel Blum, Recursive Function Theory and Speed of Computation. [REVIEW] Journal of Symbolic Logic 37 (1):199-199.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  18. Kenneth Appel (1997). Dekker JCE. Infinite Series of Isols. Recursive Function Theory, Proceedings of Symposia in Pure Mathematics, Vol. 5, American Mathematical Society, Providence 1962, Pp. 77–96. [REVIEW] Journal of Symbolic Logic 31 (4):652-652.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  19. José Félix Costa, Bruno Loff & Jerzy Mycka (2009). A Foundation for Real Recursive Function Theory. Annals of Pure and Applied Logic 160 (3):255-288.score: 45.0
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  20. Erik Ellentuck (1968). Review: John Myhill, Recursive Function Theory. [REVIEW] Journal of Symbolic Logic 33 (4):619-620.score: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  21. H. B. Enderton (1971). Review: Albert A. Mullin, On a Theorem Equivalent to Post's Fundamental Theorem of Recursive Function Theory. [REVIEW] Journal of Symbolic Logic 36 (2):343-343.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  22. Albert A. Mullin (1963). On A Theorem Equivalent to Post's Fundamental Theorem of Recursive Function Theory. Mathematical Logic Quarterly 9 (12‐15):203-205.score: 45.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  23. Stewart Shapiro (1990). Kleene Stephen C.. Origins of Recursive Function Theory. Annals of the History of Computing, Vol. 3 (1981), Pp. 52–67. Davis Martin. Why Gödel Didn't Have Church's Thesis. Information and Control, Vol. 54 (1982), Pp. 3–24. Kleene Stephen C.. Reflections on Church's Thesis. Notre Dame Journal of Formal Logic, Vol. 28 (1987), Pp. 490–498. [REVIEW] Journal of Symbolic Logic 55 (1):348-350.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  24. Norman Shapiro (1955). Review: J. R. Myhill, Three Contributions to Recursive Function Theory. [REVIEW] Journal of Symbolic Logic 20 (2):176-177.score: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  25. Mark Changizi (1996). Function Identification From Noisy Data with Recursive Error Bounds. Erkenntnis 45 (1):91 - 102.score: 43.0
    New success criteria of inductive inference in computational learning theory are introduced which model learning total (not necessarily recursive) functions with (possibly everywhere) imprecise theories from (possibly always) inaccurate data. It is proved that for any level of error allowable by the new success criteria, there exists a class of recursive functions such that not all f are identifiable via the criterion at that level of error. Also, necessary and sufficient conditions on the error level are given for (...)
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  26. Luis E. Sanchis (1992). Recursive Functionals. North-Holland.score: 42.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  
  27. László Á Kóczy (2007). A Recursive Core for Partition Function Form Games. Theory and Decision 63 (1):41-51.score: 42.0
    We present a well-defined generalisation of the core to coalitional games with externalities, where the value of a deviation is given by an endogenous response, the solution (if nonempty: the core) of the residual game.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  28. Qing Zhou (1996). Computable Real‐Valued Functions on Recursive Open and Closed Subsets of Euclidean Space. Mathematical Logic Quarterly 42 (1):379-409.score: 42.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  29. 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: 39.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  30. Guillaume Wunsch, Michel Mouchart & Federica Russo (2014). Functions and Mechanisms in Structural-Modelling Explanations. Journal for General Philosophy of Science 45 (1):187-208.score: 39.0
    One way social scientists explain phenomena is by building structural models. These models are explanatory insofar as they manage to perform a recursive decomposition on an initial multivariate probability distribution, which can be interpreted as a mechanism. Explanations in social sciences share important aspects that have been highlighted in the mechanisms literature. Notably, spelling out the functioning the mechanism gives it explanatory power. Thus social scientists should choose the variables to include in the model on the basis of their (...)
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  31. Paul Axt (1966). Review: Robert W. Ritchie, Classes of Recursive Functions Based on Ackermann's Function. [REVIEW] Journal of Symbolic Logic 31 (4):654-654.score: 39.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  32. Pavel Naumov (2005). On Modal Logics of Partial Recursive Functions. Studia Logica 81 (3):295 - 309.score: 36.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  
  33. 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: 36.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 (...) is elementary recursive. Furthermore, it is shown that, conversely, every elementary recursive function is representable in $T^{\star}$ .The expressive weakness of $T^{\star}$ compared to the full system T can be explained as follows: In contrast to $T$ , computation steps in $T^{\star}$ never increase the nesting-depth of ${\mathcal I}_\rho$ and ${\mathcal R}_\rho$ at recursion positions. (shrink)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  34. D. A. Clarke (1968). Review: Tosiyuki Tugue, On Predicates Expressible in the 1-Function Quantifier Forms in Kleene Hierarchy with Free Variables of Type 2; Tosiyuki Tugue, Predicates Recursive in a Type-2 Object and Kleene Hierarchies. [REVIEW] Journal of Symbolic Logic 33 (1):115-116.score: 36.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  35. Ján Komara (2011). On Nested Simple Recursion. Archive for Mathematical Logic 50 (5-6):617-624.score: 36.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  
  36. John N. Crossley & Michael A. E. Dummett (eds.) (1965). Formal Systems and Recursive Functions. Amsterdam, North-Holland Pub. Co..score: 35.0
    No categories
     
    My bibliography  
     
    Export citation  
  37. H. Rogers (1987). Theory of Recursive Functions and Effective Computability. Mit Press.score: 35.0
  38. Daniel E. Severin (2008). Unary Primitive Recursive Functions. Journal of Symbolic Logic 73 (4):1122-1138.score: 34.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  
  39. Karl-Heinz Niggl (1998). A Restricted Computation Model on Scott Domains and its Partial Primitive Recursive Functionals. Archive for Mathematical Logic 37 (7):443-481.score: 34.0
    The paper builds on both a simply typed term system ${\cal PR}^\omega$ and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains $D_\rho$ supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions ${\cal PR}^{\omega e}$ and PTWP $^e$ are studied (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  40. Stefano Mazzanti (1997). Iterative Characterizations of Computable Unary Functions: A General Method. Mathematical Logic Quarterly 43 (1):29-38.score: 33.0
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  41. Farzad Didehvar (1999). On a Class of Recursively Enumerable Sets. Mathematical Logic Quarterly 45 (4):467-470.score: 33.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  42. Yury P. Shimansky (2004). The Concept of a Universal Learning System as a Basis for Creating a General Mathematical Theory of Learning. Minds and Machines 14 (4):453-484.score: 31.0
    The number of studies related to natural and artificial mechanisms of learning rapidly increases. However, there is no general theory of learning that could provide a unifying basis for exploring different directions in this growing field. For a long time the development of such a theory has been hindered by nativists' belief that the development of a biological organism during ontogeny should be viewed as parameterization of an innate, encoded in the genome structure by an innate algorithm, and nothing essentially (...)
    Direct download (10 more)  
     
    My bibliography  
     
    Export citation  
  43. Karl-Heinz Niggl (1997). Non-Definability of the Ackermann Function with Type 1 Partial Primitive Recursion. Archive for Mathematical Logic 37 (1):1-13.score: 31.0
    The paper builds on a simply typed term system ${\cal PR}^\omega $ providing a notion of partial primitive recursive functional on arbitrary Scott domains $D_\sigma$ that includes a suitable concept of parallelism. Computability on the partial continuous functionals seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (SCVR) is not reducible to partial primitive recursion. So an extension ${\cal PR}^{\omega e}$ is studied that is closed under SCVR and yet stays within the realm of subrecursiveness. The (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  44. G. Lee Bowie (1982). Lucas' Number is Finally Up. Journal of Philosophical Logic 11 (3):279-85.score: 30.0
  45. Michael Rathjen (1992). A Proof-Theoretic Characterization of the Primitive Recursive Set Functions. Journal of Symbolic Logic 57 (3):954-969.score: 30.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  
  46. Cristian Calude, Gabriel Istrate & Marius Zimand (1992). Recursive Baire Classification and Speedable Functions. Mathematical Logic Quarterly 38 (1):169-178.score: 30.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  47. Dev K. Roy (2003). The Shortest Definition of a Number in Peano Arithmetic. Mathematical Logic Quarterly 49 (1):83-86.score: 30.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  48. Phil Watson (1997). Embeddings in the Strong Reducibilities Between 1 and Npm. Mathematical Logic Quarterly 43 (4):559-568.score: 30.0
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  49. 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: 30.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  
  50. W. Degen (2002). Factors of Functions, AC and Recursive Analogues. Mathematical Logic Quarterly 48 (1):73-86.score: 30.0
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
1 — 50 / 1000