Results for 'Computable functions'

1000+ found
Order:
  1.  17
    Computability Computable Functions, Logic, and the Foundations of Mathematics.Richard L. Epstein & Walter A. Carnielli - 1989
    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.  85
    The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions.Martin Davis (ed.) - 1965 - 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.  19
    The Elementary Computable Functions Over the Real Numbers: Applying Two New Techniques. [REVIEW]Manuel L. Campagnolo & Kerry Ojakian - 2008 - 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.  14
    Consistency Statements and Iterations of Computable Functions in IΣ1 and PRA.Joost J. Joosten - 2010 - 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. Derivatives of Computable Functions.Ning Zhong - 1998 - 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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  6.  2
    Uniformly Computable Aspects of Inner Functions: Estimation and Factorization.Timothy H. McNicholl - 2008 - 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.  60
    Basic Reading on Computable Functions.Peter Smith - unknown
    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
    When Series of Computable Functions with Varying Domains Are Computable.Iraj Kalantari & Larry Welch - 2013 - Mathematical Logic Quarterly 59 (6):471-493.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  9.  8
    Iterative Characterizations of Computable Unary Functions: A General Method.Stefano Mazzanti - 1997 - 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.  48
    Effective Procedures and Computable Functions.Carol E. Cleland - 1995 - 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. Computable Real‐Valued Functions on Recursive Open and Closed Subsets of Euclidean Space.Qing Zhou - 1996 - 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.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  12.  7
    Predicatively Computable Functions on Sets.Toshiyasu Arai - 2015 - Archive for Mathematical Logic 54 (3-4):471-485.
  13. Diagonally Non-Computable Functions and Bi-Immunity. Jockusch Jr & Andrew E. M. Lewis - 2013 - Journal of Symbolic Logic 78 (3):977-988.
  14. Computable Functions, Quantum Measurements, and Quantum Dynamics.M. A. Nielsen - unknown
    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  
  15.  15
    Computability. Computable Functions, Logic, and the Foundations of Mathematics. [REVIEW]R. Zach - 2002 - History and Philosophy of Logic 23 (1):67-69.
    Direct download  
     
    Export citation  
     
    My bibliography  
  16. Review: Jerome Malitz, Introduction to Mathematical Logic. Set Theory, Computable Functions, Model Theory. [REVIEW]P. Eklof - 1984 - Journal of Symbolic Logic 49 (2):672-673.
     
    Export citation  
     
    My bibliography  
  17.  12
    Formulas for Computable and Non-Computable Functions.Samuel Alexander - 2006 - Rose-Hulman Undergraduate Mathematics Journal 7 (2).
    Translate
      Direct download  
     
    Export citation  
     
    My bibliography  
  18.  5
    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]Stefan Bauer-Mengelberg - 1996 - Journal of Symbolic Logic 31 (3):484-494.
  19.  9
    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]Carlos Augusto Priscdio - 2002 - Bulletin of Symbolic Logic 8 (1):101-104.
  20. Review: Robert W. Ritchie, Classes of Predictably Computable Functions[REVIEW]C. C. Elgot - 1963 - Journal of Symbolic Logic 28 (3):252-253.
  21.  4
    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]Simon Thompson - 2001 - Manuscrito 24 (1):245-256.
  22. Review: Robert I. Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets. [REVIEW]Eberhard Herrmann & Rodney Downey - 1990 - Journal of Symbolic Logic 55 (1):356-357.
  23.  3
    On the Convergence of Fourier Series of Computable Lebesgue Integrable Functions.Philippe Moser - 2010 - 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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  24. Review: T. Rado, On Non-Computable Functions[REVIEW]F. B. Cannonito - 1967 - Journal of Symbolic Logic 32 (4):524-524.
  25.  2
    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]Carlos Augusto Di Prisco - 2002 - Bulletin of Symbolic Logic 8 (1):101-104.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  26. Review: Tibor Rado, On a Simple Source for Non-Computable Functions[REVIEW]F. B. Cannonito - 1967 - Journal of Symbolic Logic 32 (4):524-524.
  27.  1
    Review: G. S. Matveeva, On a Theorem of Rabin Concerning the Complexity of Computable Functions[REVIEW]Jiri Becvar - 1969 - Journal of Symbolic Logic 34 (1):133-134.
  28.  1
    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]Carlos Augusto di Prisco - 2002 - Bulletin of Symbolic Logic 8 (1):101-104.
    Direct download  
     
    Export citation  
     
    My bibliography  
  29. Rado Tibor. On a Simple Source for Non-Computable Functions. Proceedings of the Symposium on Mathematical Theory of Automata, New York, N.Y., April 24, 25, 26, 1962, Microwave Research Institute Symposia Series Vol. 12, Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn, N.Y., 1963, Pp. 75–81. [REVIEW]F. B. Cannonito - 1968 - Journal of Symbolic Logic 32 (4):524.
  30. Rado T.. On Non-Computable Functions. The Bell System Technical Journal, Vol. 41 , Pp. 877–884.F. B. Cannonito - 1968 - Journal of Symbolic Logic 32 (4):524.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  31. Local Induction and Provably Total Computable Functions: A Case Study.Andrés Cordón–Franco & F. Félix Lara–Martín - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 440--449.
    Direct download  
     
    Export citation  
     
    My bibliography  
  32. 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]Carlos Augusto Di Prisco - 2002 - Bulletin of Symbolic Logic 8 (1):101-104.
  33. Malitz Jerome. Introduction to Mathematical Logic. Set Theory, Computable Functions, Model Theory. Undergraduate Texts in Mathematics. Springer-Verlag, New York, Heidelberg, and Berlin, 1979, Xii + 198 Pp. [REVIEW]P. Eklof - 1984 - Journal of Symbolic Logic 49 (2):672-673.
  34. Ritchie Robert W.. Classes of Predictably Computable Functions. Transactions of the American Mathematical Society, Vol. 106 , Pp. 139–173. [REVIEW]C. C. Elgot - 1963 - Journal of Symbolic Logic 28 (3):252-253.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  35. Computability. Computable Functions, Logic, and the Foundations of Mathematics.L. Epstein Richard & A. Carnielli Walter - 2002 - Bulletin of Symbolic Logic 8 (1):101-104.
    Direct download  
     
    Export citation  
     
    My bibliography  
  36. Soare Robert I.. Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, Heidelberg, New York, Etc., 1987, Xviii + 437 Pp. [REVIEW]Eberhard Herrmann & Rodney Downey - 1990 - Journal of Symbolic Logic 55 (1):356-357.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  37. Review: V. A. Uspenskij, (Lekcii o Vycislimyh Funkciah)Lectures on Computable Functions[REVIEW]Elliott Mendelson - 1966 - Journal of Symbolic Logic 31 (2):263-264.
  38. Computability. Computable Functions, Logic, and the Foundations of MathematicsComputability. Computable Functions, Logic, and the Foundations of Mathematics. Second Edition of the Preceding. [REVIEW]Carlos Augusto Di Prisco, Richard L. Epstein & Walter A. Carnielli - 2002 - Bulletin of Symbolic Logic 8 (1):101.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  39.  13
    Euclidean Functions of Computable Euclidean Domains.Rodney G. Downey & Asher M. Kach - 2011 - 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  
  40.  19
    Limitwise Monotonic Functions, Sets, and Degrees on Computable Domains.Asher M. Kach & Daniel Turetsky - 2010 - 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 (6 more)  
     
    Export citation  
     
    My bibliography  
  41.  1
    Computable Choice Functions for Computable Linear Orderings.Manuel Lerman & Richard Watnick - 2003 - 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  
  42.  20
    Theory of Recursive Functions and Effective Computability.H. Rogers - 1987 - MIT Press.
  43.  3
    On a Simple Definition of Computable Function of a Real Variable‐with Applications to Functions of a Complex Variable.Marian Boykan Pour‐El & Jerome Caldwell - 1975 - Mathematical Logic Quarterly 21 (1):1-19.
  44.  14
    A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs.Asae Mochizuki & Juichi Shinoda - 1996 - Annals of the Japan Association for Philosophy of Science 9 (1):17-21.
  45.  14
    Functions Computable by a Computer.A. Schurmann - 1971 - Studia Logica 27 (1):57 - 72.
  46.  4
    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]Jiří Bečvář - 1997 - Journal of Symbolic Logic 31 (4):656-657.
  47.  1
    Bertoni A.. Mathematical Methods of the Theory of Stochastic Automata. Mathematical Foundations of Computer Science, 3rd Symposium at Jadwisin Near Warsaw, June 17–22, 1974, Edited by Blikle A., Lecture Notes in Computer Science, Vol. 28, Springer-Verlag, Berlin, Heidelberg, and New York, 1975, Pp. 9–22.Freivald R. V.. Functions Computable in the Limit by Probabilistic Machines. Mathematical Foundations of Computer Science, 3rd Symposium at Jadwisin Near Warsaw, June 17–22, 1974, Edited by Blikle A., Lecture Notes in Computer Science, Vol. 28, Springer-Verlag, Berlin, Heidelberg, and New York, 1975, Pp. 77–87.Goetze B. And Klette R.. Some Properties of Limit Recursive Functions. Mathematical Foundations of Computer Science, 3rd Symposium at Jadwisin Near Warsaw, June 17–22, 1974, Edited by Blikle A., Lecture Notes in Computer Science, Vol. 28, Springer-Verlag, Berlin, Heidelberg, and New York, 1975, Pp. 88–90.Dahl Ole-Johan. An Approach to Correctness Proofs of Semicoroutines. Mathemat. [REVIEW]Steven S. Muchnick - 1977 - Journal of Symbolic Logic 42 (3):422-423.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  48.  2
    Effective Enumerability of Some Families of Partially Recursive Functions Connected With Computable Functionals.Vladeta Vučković - 1970 - Mathematical Logic Quarterly 16 (2):113-121.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  49.  1
    A Term Rewriting Characterization of the Functions Computable in Polynomial Space.Isabel Oitavem - 2002 - Archive for Mathematical Logic 41 (1):35-47.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  50.  1
    Review: Hisao Yamada, Real-Time Computation and Recursive Functions Not Real-Time Computable[REVIEW]Jiri Becvar - 1966 - Journal of Symbolic Logic 31 (4):656-657.
1 — 50 / 1000