Search results for 'Computable functions' (try it on Scholar)

1000+ found
Order:
  1.  1
    Richard L. Epstein & Walter A. Carnielli (1989). Computability Computable Functions, Logic, and the Foundations of Mathematics. Monograph Collection (Matt - Pseudo).
    This book is dedicated to a classic presentation of the theory of computable functions in the context of the foundations of mathematics. Part I motivates the study of computability with discussions and readings about the crisis in the foundations of mathematics in the early 20th century, while presenting the basic ideas of whole number, function, proof, and real number. Part II starts with readings from Turing and Post leading to the formal theory of recursive functions. Part III (...)
    Direct download  
     
    Export citation  
     
    My bibliography   4 citations  
  2.  79
    Martin Davis (ed.) (1965/2004). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions. Dover Publication.
    "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  
     
    Export citation  
     
    My bibliography   32 citations  
  3.  17
    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.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  4.  11
    Joost J. Joosten (2010). Consistency Statements and Iterations of Computable Functions in IΣ1 and PRA. Archive for Mathematical Logic 49 (7-8):773-798.
    In this paper we will state and prove some comparative theorems concerning PRA and IΣ1. We shall provide a characterization of IΣ1 in terms of PRA and iterations of a class of functions. In particular, we prove that for this class of functions the difference between IΣ1 and PRA is exactly that, where PRA is closed under iterations of these functions, IΣ1 is moreover provably closed under iteration. We will formulate a sufficient condition for a model of (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  5. Ning Zhong (1998). Derivatives of Computable Functions. Mathematical Logic Quarterly 44 (3):304-316.
    As is well known the derivative of a computable and C1 function may not be computable. For a computable and C∞ function f, the sequence {f} of its derivatives may fail to be computable as a sequence, even though its derivative of any order is computable. In this paper we present a necessary and sufficient condition for the sequence {f} of derivatives of a computable and C∞ function f to be computable. We also (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  6.  1
    Timothy H. McNicholl (2008). Uniformly Computable Aspects of Inner Functions: Estimation and Factorization. Mathematical Logic Quarterly 54 (5):508-518.
    The theory of inner functions plays an important role in the study of bounded analytic functions. Inner functions are also useful in applied mathematics. Two foundational results in this theory are Frostman's Theorem and the Factorization Theorem. We prove a uniformly computable version of Frostman's Theorem. We then show that the Factorization Theorem is not uniformly computably true. We then show that for an inner function u with infinitely many zeros, the Blaschke sum of u provides (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  7.  57
    Peter Smith, Basic Reading on Computable Functions.
    This is an annotated reading list on the beginning elements of the theory of computable functions. It is now structured so as to complement the first eight lectures of Thomas Forster’s Part III course in Lent 2011 (see the first four chapters of his evolving handouts).
    Direct download  
     
    Export citation  
     
    My bibliography  
  8.  2
    Iraj Kalantari & Larry Welch (2013). When Series of Computable Functions with Varying Domains Are Computable. Mathematical Logic Quarterly 59 (6):471-493.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  9.  8
    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  
  10.  44
    Carol E. Cleland (1995). Effective Procedures and Computable Functions. Minds and Machines 5 (1):9-23.
    Horsten and Roelants have raised a number of important questions about my analysis of effective procedures and my evaluation of the Church-Turing thesis. They suggest that, on my account, effective procedures cannot enter the mathematical world because they have a built-in component of causality, and, hence, that my arguments against the Church-Turing thesis miss the mark. Unfortunately, however, their reasoning is based upon a number of misunderstandings. Effective mundane procedures do not, on my view, provide an analysis of ourgeneral concept (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  11. 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  
  12. M. A. Nielsen, Computable Functions, Quantum Measurements, and Quantum Dynamics.
    Quantum mechanical measurements on a physical system are represented by observables - Hermitian operators on the state space of the observed system. It is an important question whether all observables may be realized, in principle, as measurements on a physical system. Dirac’s influential text ( [1], page 37) makes the following assertion on the question: The question now presents itself – Can every observable be measured? The answer theoretically is yes. In practice it may be very awkward, or perhaps even (...)
    Translate
     
     
    Export citation  
     
    My bibliography  
  13.  8
    R. Zach (2002). Computability. Computable Functions, Logic, and the Foundations of Mathematics. [REVIEW] History and Philosophy of Logic 23 (1):67-69.
    Direct download  
     
    Export citation  
     
    My bibliography  
  14.  6
    Toshiyasu Arai (2015). Predicatively Computable Functions on Sets. Archive for Mathematical Logic 54 (3-4):471-485.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  15. P. Eklof (1984). Review: Jerome Malitz, Introduction to Mathematical Logic. Set Theory, Computable Functions, Model Theory. [REVIEW] Journal of Symbolic Logic 49 (2):672-673.
     
    Export citation  
     
    My bibliography  
  16.  11
    Samuel Alexander (2006). Formulas for Computable and Non-Computable Functions. Rose-Hulman Undergraduate Mathematics Journal 7 (2).
    Translate
      Direct download  
     
    Export citation  
     
    My bibliography  
  17.  4
    Simon Thompson (2001). Resenha de 'Propositional Logic: The Semantic Foundations of Logic' (R. L. Epstein) - 'Predicate Logic: The Semantic Foundations of Logic' (R. L. Epstein) - 'Computable Functions, Logic, and the Foundations of Mathematics' (R. L. Epstein and W. A. Carniel). [REVIEW] Manuscrito 24 (1).
  18.  4
    Stefan Bauer-Mengelberg (1996). Davis Martin. On Formally Undecidable Propositions of the Principia Mathematica and Related Systems. I. The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Edited by Davis Martin, Raven Press, Hewlett, New York, 1965, P. 4. Gödel Kurt. On Formally Undecidable Propositions of Principia Mathematica and Related Systems I. English Translation of 4183 by Elliott Mendelson. The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems and ... [REVIEW] Journal of Symbolic Logic 31 (3):484-494.
    Direct download  
     
    Export citation  
     
    My bibliography  
  19. C. C. Elgot (1963). Review: Robert W. Ritchie, Classes of Predictably Computable Functions. [REVIEW] Journal of Symbolic Logic 28 (3):252-253.
     
    Export citation  
     
    My bibliography  
  20. Eberhard Herrmann & Rodney Downey (1990). Review: Robert I. Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets. [REVIEW] Journal of Symbolic Logic 55 (1):356-357.
     
    Export citation  
     
    My bibliography  
  21.  6
    Carlos Augusto Priscdio (2002). Review: Richard L. Epstein, Walter A. Carnielli, Computability. Computable Functions, Logic, and the Foundations of Mathematics ; Richard L. Epstein, Walter A. Carnielli, Computability. Computable Functions, Logic, and the Foundations of Mathematics. Second Edition of the Preceding. [REVIEW] Bulletin of Symbolic Logic 8 (1):101-104.
  22.  2
    Carlos Augusto Di Prisco (2002). Review: Richard L. Epstein, Walter A. Carnielli, Computability. Computable Functions, Logic, and the Foundations of Mathematics; Richard L. Epstein, Walter A. Carnielli, Computability. Computable Functions, Logic, and the Foundations of Mathematics. Second Edition of the Preceding. [REVIEW] Bulletin of Symbolic Logic 8 (1):101-104.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  23.  2
    Philippe Moser (2010). On the Convergence of Fourier Series of Computable Lebesgue Integrable Functions. Mathematical Logic Quarterly 56 (5):461-469.
    This paper studies how well computable functions can be approximated by their Fourier series. To this end, we equip the space of Lp-computable functions with a size notion, by introducing Lp-computable Baire categories. We show that Lp-computable Baire categories satisfy the following three basic properties. Singleton sets {f } are meager, suitable infinite unions of meager sets are meager, and the whole space of Lp-computable functions is not meager. We give an alternative (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  24. F. B. Cannonito (1967). Review: T. Rado, On Non-Computable Functions. [REVIEW] Journal of Symbolic Logic 32 (4):524-524.
     
    Export citation  
     
    My bibliography  
  25.  3
    Carlos Augusto Priscdio (2002). Review: Richard L. Epstein, Walter A. Carnielli, Computability. Computable Functions, Logic, and the Foundations of Mathematics ; Richard L. Epstein, Walter A. Carnielli, Computability. Computable Functions, Logic, and the Foundations of Mathematics. Second Edition of the Preceding. [REVIEW] Bulletin of Symbolic Logic 8 (1):101-104.
  26. F. B. Cannonito (1967). Review: Tibor Rado, On a Simple Source for Non-Computable Functions. [REVIEW] Journal of Symbolic Logic 32 (4):524-524.
     
    Export citation  
     
    My bibliography  
  27. Jiri Becvar (1969). Review: G. S. Matveeva, On a Theorem of Rabin Concerning the Complexity of Computable Functions. [REVIEW] Journal of Symbolic Logic 34 (1):133-134.
    Direct download  
     
    Export citation  
     
    My bibliography  
  28. Andrés Cordón–Franco & F. Félix Lara–Martín (2012). Local Induction and Provably Total Computable Functions: A Case Study. In S. Barry Cooper (ed.), How the World Computes. 440--449.
    Direct download  
     
    Export citation  
     
    My bibliography  
  29. Carlos Augusto di Prisco (2002). Epstein Richard L. And Carnielli Walter A.. Computability. Computable Functions, Logic, and the Foundations of Mathematics. The Wadsworth & Brooks/Cole Mathematics Series. Wadsworth&Brooks/Cole Advanced Books & Software, Pacific Grove, Calif., 1989, Xvii+ 297 Pp. Epstein Richard L. And Carnielli Walter A.. Computability. Computable Functions, Logic, and the Foundations of Mathematics. Of the Preceding. Wadsworth, Belmont, Calif., Etc., 2000, Xii+ 299+ 38 Pp. [REVIEW] Bulletin of Symbolic Logic 8 (1):101-104.
    Direct download  
     
    Export citation  
     
    My bibliography  
  30. Carlos Augusto Di Prisco (2002). Review: Richard L. Epstein, Walter A. Carnielli, Computability. Computable Functions, Logic, and the Foundations of Mathematics; Richard L. Epstein, Walter A. Carnielli, Computability. Computable Functions, Logic, and the Foundations of Mathematics. Of the Preceding. [REVIEW] Bulletin of Symbolic Logic 8 (1):101-104.
    Direct download  
     
    Export citation  
     
    My bibliography  
  31. Elliott Mendelson (1966). Review: V. A. Uspenskij, (Lekcii o Vycislimyh Funkciah)Lectures on Computable Functions. [REVIEW] Journal of Symbolic Logic 31 (2):263-264.
    Translate
     
     
    Export citation  
     
    My bibliography  
  32.  11
    Rodney G. Downey & Asher M. Kach (2010). Euclidean Functions of Computable Euclidean Domains. Notre Dame Journal of Formal Logic 52 (2):163-172.
    We study the complexity of (finitely-valued and transfinitely-valued) Euclidean functions for computable Euclidean domains. We examine both the complexity of the minimal Euclidean function and any Euclidean function. Additionally, we draw some conclusions about the proof-theoretical strength of minimal Euclidean functions in terms of reverse mathematics.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  33.  17
    Asher M. Kach & Daniel Turetsky (2010). Limitwise Monotonic Functions, Sets, and Degrees on Computable Domains. Journal of Symbolic Logic 75 (1):131-154.
    We extend the notion of limitwise monotonic functions to include arbitrary computable domains. We then study which sets and degrees are support increasing limitwise monotonic on various computable domains. As applications, we provide a characterization of the sets S with computable increasing η-representations using support increasing limitwise monotonic sets on ℚ and note relationships between the class of order-computable sets and the class of support increasing limitwise monotonic sets on certain domains.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  34.  1
    Manuel Lerman & Richard Watnick (2003). Computable Choice Functions for Computable Linear Orderings. Mathematical Logic Quarterly 49 (5):485-510.
    A choice set for a computable linear ordering is a set which contains one element from each maximal block of the ordering. We obtain a partial characterization of the computable linear order-types for which each computable model has a computable choice set, and a full characterization in the relativized case; Every model of the linear order-type α of degree ≤ d has a choice set of degree ≤ d iff α can written as a finite sum (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  35.  8
    H. Rogers (1987). Theory of Recursive Functions and Effective Computability. MIT Press.
  36. Asae Mochizuki & Juichi Shinoda (1996). A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs. Annals of the Japan Association for Philosophy of Science 9 (1):17-21.
     
    Export citation  
     
    My bibliography  
  37.  10
    A. Schurmann (1971). Functions Computable by a Computer. Studia Logica 27 (1):57 - 72.
  38.  2
    Marian Boykan Pour‐El & Jerome Caldwell (1975). On a Simple Definition of Computable Function of a Real Variable‐with Applications to Functions of a Complex Variable. Mathematical Logic Quarterly 21 (1):1-19.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  39.  2
    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.
    Direct download  
     
    Export citation  
     
    My bibliography  
  40.  1
    Jiri Becvar (1966). Review: Hisao Yamada, Real-Time Computation and Recursive Functions Not Real-Time Computable. [REVIEW] Journal of Symbolic Logic 31 (4):656-657.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  41.  1
    J. Tucker & J. Zucker (1992). Provable Computable Selection Functions on Abstract Structures. In Peter Aczel, Harold Simmons & S. S. Wainer (eds.), Proof Theory: A Selection of Papers From the Leeds Proof Theory Programme, 1990. Cambridge University Press 275.
    Direct download  
     
    Export citation  
     
    My bibliography  
  42.  1
    Vladeta Vučković (1970). Effective Enumerability of Some Families of Partially Recursive Functions Connected With Computable Functionals. Mathematical Logic Quarterly 16 (2):113-121.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  43. Isabel Oitavem (2002). A Term Rewriting Characterization of the Functions Computable in Polynomial Space. Archive for Mathematical Logic 41 (1):35-47.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  44. Stefano Mazzanti (2005). Bounded Iteration and Unary Functions. Mathematical Logic Quarterly 51 (1):89-94.
    The set of unary functions of complexity classes defined by using bounded primitive recursion is inductively characterized by means of bounded iteration. Elementary unary functions, linear space computable unary functions and polynomial space computable unary functions are then inductively characterized using only composition and bounded iteration.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  45.  10
    Vasco Brattka (2005). Effective Borel Measurability and Reducibility of Functions. Mathematical Logic Quarterly 51 (1):19-44.
    The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single-valued as well as for multi-valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for (...)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   11 citations  
  46.  1
    D. Kunkle (2004). Type-2 Computability on Spaces of Integrables Functions. Mathematical Logic Quarterly 50 (4):417.
    Using Type-2 theory of effectivity, we define computability notions on the spaces of Lebesgue-integrable functions on the real line that are based on two natural approaches to integrability from measure theory. We show that Fourier transform and convolution on these spaces are computable operators with respect to these representations. By means of the orthonormal basis of Hermite functions in L2, we show the existence of a linear complexity bound for the Fourier transform.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  47. C. J. Ash (2000). Computable Structures and the Hyperarithmetical Hierarchy. Elsevier.
    This book describes a program of research in computable structure theory. The goal is to find definability conditions corresponding to bounds on complexity which persist under isomorphism. The results apply to familiar kinds of structures (groups, fields, vector spaces, linear orderings Boolean algebras, Abelian p-groups, models of arithmetic). There are many interesting results already, but there are also many natural questions still to be answered. The book is self-contained in that it includes necessary background material from recursion theory (ordinal (...)
    Direct download  
     
    Export citation  
     
    My bibliography   11 citations  
  48.  76
    Martin Davis (1958/1982). Computability & Unsolvability. Dover.
    Classic text considersgeneral theory of computability, computable functions, operations on computable functions, Turing machines self-applied, unsolvable decision problems, applications of general theory, mathematical logic, Kleene hierarchy, computable functionals, classification of unsolvable decision problems and more.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   82 citations  
  49.  8
    H. E. Rose (1984). Subrecursion: Functions and Hierarchies. Oxford University Press.
  50.  98
    George Boolos, John Burgess, Richard P. & C. Jeffrey (2007). Computability and Logic. Cambridge University Press.
    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 functions, (...)
    Direct download  
     
    Export citation  
     
    My bibliography   90 citations  
1 — 50 / 1000