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

1000+ found
Order:
  1.  5
    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.
    Although the theory of definability had many important antecedents—such as the descriptive set theory initiated by the French semi-intuitionists in the early 1900s—the main ideas were first laid out in precise mathematical terms by Alfred Tarski beginning in 1929. We review here the basic notions of languages, explicit definability, and grammatical complexity, and emphasize common themes in the theories of definability for four important languages underlying, respectively, descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic. (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  2.  12
    H. R. Strong (1970). Construction of Models for Algebraically Generalized Recursive Function Theory. Journal of Symbolic Logic 35 (3):401-409.
    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)  
     
    Export citation  
     
    My bibliography   1 citation  
  3.  1
    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.
    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 functions, e.g., (...), 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 (3 more)  
     
    Export citation  
     
    My bibliography  
  4.  41
    Nigel Cutland (1980). Computability, an Introduction to Recursive Function Theory. 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). (...)
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   8 citations  
  5.  4
    Albert A. Mullin (1963). On A Theorem Equivalent to Post's Fundamental Theorem of Recursive Function Theory. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 9 (12-15):203-205.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  6.  17
    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.
    Direct download  
     
    Export citation  
     
    My bibliography  
  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.
     
    Export citation  
     
    My bibliography  
  8.  5
    Stephen C. Kleene & Martin Davis (1990). Origins of Recursive Function Theory. Journal of Symbolic Logic 55 (1):348-350.
    Direct download  
     
    Export citation  
     
    My bibliography  
  9.  6
    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.
    Direct download  
     
    Export citation  
     
    My bibliography  
  10. H. B. Enderton (1987). Review: Nigel Cutland, Computability. An Introduction to Recursive Function Theory. [REVIEW] Journal of Symbolic Logic 52 (1):292-293.
     
    Export citation  
     
    My bibliography  
  11.  1
    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.
    Direct download  
     
    Export citation  
     
    My bibliography  
  12.  1
    Erik Ellentuck (1968). Review: John Myhill, Recursive Function Theory. [REVIEW] Journal of Symbolic Logic 33 (4):619-620.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  13.  6
    Heinrich Rolletschek (1983). Closure Properties of Almost-Finiteness Classes in Recursive Function Theory. Journal of Symbolic Logic 48 (3):756-763.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  14.  6
    R. L. Goodstein (1953). A Problem in Recursive Function Theory. Journal of Symbolic Logic 18 (3):225-232.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  15. Gustav Hensel (1966). Review: H. B. Enderton, Hierarchies in Recursive Function Theory. [REVIEW] Journal of Symbolic Logic 31 (2):262-263.
     
    Export citation  
     
    My bibliography  
  16.  1
    Julia Robinson (1972). Review: Martin Davis, Application of Recursive Function Theory to Number Theory. [REVIEW] Journal of Symbolic Logic 37 (3):602-602.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  17.  1
    Paul Young (1972). Review: Manuel Blum, Recursive Function Theory and Speed of Computation. [REVIEW] Journal of Symbolic Logic 37 (1):199-199.
    Direct download  
     
    Export citation  
     
    My bibliography  
  18.  1
    J. P. Cleave (1974). Review: Webb Miller, Recursive Function Theory and Numerical Analysis. [REVIEW] Journal of Symbolic Logic 39 (2):346-346.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  19.  1
    Joseph S. Ullian (1975). Review: Ann Yasuhara, Recursive Function Theory and Logic. [REVIEW] Journal of Symbolic Logic 40 (4):619-620.
    Direct download  
     
    Export citation  
     
    My bibliography  
  20. 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.
    Direct download  
     
    Export citation  
     
    My bibliography  
  21. 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.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  22. John Myhill (1968). Recursive Function Theory. Journal of Symbolic Logic 33 (4):619-620.
    Direct download  
     
    Export citation  
     
    My bibliography  
  23. Norman Shapiro (1955). Review: J. R. Myhill, Three Contributions to Recursive Function Theory. [REVIEW] Journal of Symbolic Logic 20 (2):176-177.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  24.  13
    László Á Kóczy (2007). A Recursive Core for Partition Function Form Games. Theory and Decision 63 (1):41-51.
    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)  
     
    Export citation  
     
    My bibliography   1 citation  
  25.  6
    Mark Changizi (1996). Function Identification From Noisy Data with Recursive Error Bounds. Erkenntnis 45 (1):91 - 102.
    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)  
     
    Export citation  
     
    My bibliography  
  26.  3
    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.
    Direct download  
     
    Export citation  
     
    My bibliography  
  27.  1
    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.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  28. 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.
     
    Export citation  
     
    My bibliography  
  29.  4
    Klaus‐Hilmar Sprenger (1997). Some Hierarchies of Primitive Recursive Functions on Term Algebras. Mathematical Logic Quarterly 43 (2):251-286.
  30.  2
    Holger Petersen (1996). The Computation of Partial Recursive Word‐Functions Without Read Instructions. Mathematical Logic Quarterly 42 (1):312-318.
    In this note we consider register-machines with symbol manipulation capabilities. They can form words over a given alphabet in their registers by appending symbols to the strings already stored. These machines are similar to Post's normal systems and the related machine-models discussed in the literature. But unlike the latter devices they are deterministic and are not allowed to read symbols from the front of the registers. Instead they can compare registers and erase them. At first glance it is surprising that (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  31. Qing Zhou (1996). Computable Real‐Valued Functions on Recursive Open and Closed Subsets of Euclidean Space. Mathematical Logic Quarterly 42 (1):379-409.
    In this paper we study intrinsic notions of “computability” for open and closed subsets of Euclidean space. Here we combine together the two concepts, computability on abstract metric spaces and computability for continuous functions, and delineate the basic properties of computable open and closed sets. The paper concludes with a comprehensive examination of the Effective Riemann Mapping Theorem and related questions.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  32.  8
    Guillaume Wunsch, Michel Mouchart & Federica Russo (2014). Functions and Mechanisms in Structural-Modelling Explanations. Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 45 (1):187-208.
    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)  
     
    Export citation  
     
    My bibliography  
  33.  5
    Iraj Kalantari & Larry Welch (2004). Density and Baire Category in Recursive Topology. Mathematical Logic Quarterly 50 (4‐5):381-391.
    We develop the concepts of recursively nowhere dense sets and sets that are recursively of first category and study closed sets of points in light of Baire's Category Theorem. Our theorems are primarily concerned with exdomains of recursive quantum functions and hence with avoidable points . An avoidance function is a recursive function which can be used to expel avoidable points from domains of recursive quantum functions. We define an avoidable set of points to be (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  34.  8
    Alexander Kreuzer & Ulrich Kohlenbach (2009). Ramsey's Theorem for Pairs and Provably Recursive Functions. 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 functionals). (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  35.  4
    Dev K. Roy (2003). The Shortest Definition of a Number in Peano Arithmetic. Mathematical Logic Quarterly 49 (1):83-86.
    The shortest definition of a number by a first order formula with one free variable, where the notion of a formula defining a number extends a notion used by Boolos in a proof of the Incompleteness Theorem, is shown to be non computable. This is followed by an examination of the complexity of sets associated with this function.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  36. M. B. Thuraisingham (1993). System Function Languages. Mathematical Logic Quarterly 39 (1):357-366.
    In this paper we define the concept of a system function language which is a language generated by a system function. We identify system function languages with recursively enumerable sets which are non-simple and co-infinite. We then define restricted system function languages and identify them with recursive sets which are co-infinite. Finally we state and prove some independence and dependence relationships between system function languages and some of the more well-known decision problems. MSC: 03D05, (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  37. J. S. Moore, R. S. Boyer & R. E. Shostak, Primitive Recursive Program Transformation.
    arbitrary flowchart programs by introducing a new recursive function for each tag point. In the above example, one obtains: int = int1, p..... 1 h ), w...., y2r )_.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography  
  38.  3
    Iraj Kalantari & Lawrence Welch (1999). Recursive and Nonextendible Functions Over the Reals; Filter Foundation for Recursive Analysis.II. 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 exist in (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  39.  71
    G. Lee Bowie (1982). Lucas' Number is Finally Up. Journal of Philosophical Logic 11 (3):279-85.
  40.  9
    Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet (2006). Enumerations of the Kolmogorov Function. Journal of Symbolic Logic 71 (2):501 - 528.
    A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  41.  13
    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.
    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)  
     
    Export citation  
     
    My bibliography   1 citation  
  42.  9
    Pavel Naumov (2005). On Modal Logics of Partial Recursive Functions. 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  
     
    My bibliography   1 citation  
  43.  4
    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.
    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)  
     
    Export citation  
     
    My bibliography   1 citation  
  44.  5
    Stefano Mazzanti (1997). Iterative Characterizations of Computable Unary Functions: A General Method. Mathematical Logic Quarterly 43 (1):29-38.
    Iterative characterizations of computable unary functions are useful patterns for the definition of programming languages based on iterative constructs. The features of such a characterization depend on the pairing producing it: this paper offers an infinite class of pairings involving very nice features.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  45.  14
    E. W. Madison & B. Zimmermann-Huisgen (1986). Combinatorial and Recursive Aspects of the Automorphism Group of the Countable Atomless Boolean Algebra. Journal of Symbolic Logic 51 (2):292-301.
    Given an admissible indexing φ of the countable atomless Boolean algebra B, an automorphism F of B is said to be recursively presented (relative to φ) if there exists a recursive function $p \in \operatorname{Sym}(\omega)$ such that F ⚬ φ = φ ⚬ p. Our key result on recursiveness: Both the subset of $\operatorname{Aut}(\mathscr{B})$ consisting of all those automorphisms which are recursively presented relative to some indexing, and its complement, the set of all "totally nonrecursive" automorphisms, are uncountable. (...)
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  46.  5
    Yuri Matiyasevich (1994). A Direct Method for Simulating Partial Recursive Functions by Diophantine Equations. 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 (3 more)  
     
    Export citation  
     
    My bibliography  
  47.  4
    Phil Watson (1997). Embeddings in the Strong Reducibilities Between 1 and Npm. Mathematical Logic Quarterly 43 (4):559-568.
    We consider the strongest forms of enumeration reducibility, those that occur between 1- and npm-reducibility inclusive. By defining two new reducibilities which are counterparts to 1- and i-reducibility, respectively, in the same way that nm- and npm-reducibility are counterparts to m- and pm-reducibility, respectively, we bring out the structure of the strong reducibilities. By further restricting n1- and nm-reducibility we are able to define infinite families of reducibilities which isomorphically embed the r. e. Turing degrees. Thus the many well-known results (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  48.  1
    Farzad Didehvar (1999). On a Class of Recursively Enumerable Sets. Mathematical Logic Quarterly 45 (4):467-470.
    We define a class of so-called ∑-sets as a natural closure of recursively enumerable sets Wn under the relation “∈” and study its properties.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  49. Michael Rathjen (1992). A Proof-Theoretic Characterization of the Primitive Recursive Set Functions. Journal of Symbolic Logic 57 (3):954-969.
    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)  
     
    Export citation  
     
    My bibliography   5 citations  
  50.  6
    Lev D. Beklemishev (1997). Induction Rules, Reflection Principles, and Provably Recursive Functions. 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 (3 more)  
     
    Export citation  
     
    My bibliography   7 citations  
1 — 50 / 1000