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

1000+ found
Sort by:
  1. Martin Davis (ed.) (1965/2004). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions. Dover Publication.score: 87.0
    "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  
     
    My bibliography  
     
    Export citation  
  2. 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: 84.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  
  3. 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.score: 78.0
    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 (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Ning Zhong (1998). Derivatives of Computable Functions. Mathematical Logic Quarterly 44 (3):304-316.score: 69.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. Peter Smith, Basic Reading on Computable Functions.score: 60.0
    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).
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  6. Timothy H. McNicholl (2008). Uniformly Computable Aspects of Inner Functions: Estimation and Factorization. Mathematical Logic Quarterly 54 (5):508-518.score: 60.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  7. Nigel Cutland (1980). Computability, an Introduction to Recursive Function Theory. Cambridge University Press.score: 57.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). Dr (...)
    Direct download  
     
    My bibliography  
     
    Export citation  
  8. Carol E. Cleland (1995). Effective Procedures and Computable Functions. Minds and Machines 5 (1):9-23.score: 53.0
    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 (6 more)  
     
    My bibliography  
     
    Export citation  
  9. Iraj Kalantari & Larry Welch (2013). When Series of Computable Functions with Varying Domains Are Computable. Mathematical Logic Quarterly 59 (6):471-493.score: 51.0
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Rodney G. Downey & Asher M. Kach (2010). Euclidean Functions of Computable Euclidean Domains. Notre Dame Journal of Formal Logic 52 (2):163-172.score: 50.0
    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)  
     
    My bibliography  
     
    Export citation  
  11. Asher M. Kach & Daniel Turetsky (2010). Limitwise Monotonic Functions, Sets, and Degrees on Computable Domains. Journal of Symbolic Logic 75 (1):131-154.score: 50.0
    We extend the notion of limitwise monotonic functions to include arbitrary computable domains. We then study which sets and degrees are support increasing (support strictly 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 ${\Bbb Q}$ and note relationships between the class of order-computable sets and the class of support increasing (support strictly increasing) limitwise monotonic sets (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  12. Stefano Mazzanti (1997). Iterative Characterizations of Computable Unary Functions: A General Method. Mathematical Logic Quarterly 43 (1):29-38.score: 50.0
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  13. Qing Zhou (1996). Computable Real‐Valued Functions on Recursive Open and Closed Subsets of Euclidean Space. Mathematical Logic Quarterly 42 (1):379-409.score: 50.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  14. Nachum Dershowitz & Yuri Gurevich (2008). A Natural Axiomatization of Computability and Proof of Church's Thesis. Bulletin of Symbolic Logic 14 (3):299-350.score: 48.0
    Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a (...)
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  15. Martin Davis (1958/1982). Computability & Unsolvability. Dover.score: 48.0
    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  
     
    My bibliography  
     
    Export citation  
  16. Lawrence C. Paulson (1987). Logic and Computation: Interactive Proof with Cambridge Lcf. Cambridge University Press.score: 48.0
    Logic and Computation is concerned with techniques for formal theorem-proving, with particular reference to Cambridge LCF (Logic for Computable Functions). Cambridge LCF is a computer program for reasoning about computation. It combines methods of mathematical logic with domain theory, the basis of the denotational approach to specifying the meaning of statements in a programming language. This book consists of two parts. Part I outlines the mathematical preliminaries: elementary logic and domain theory. They are explained at an intuitive level, (...)
    Direct download  
     
    My bibliography  
     
    Export citation  
  17. Manuel Lerman & Richard Watnick (2003). Computable Choice Functions for Computable Linear Orderings. Mathematical Logic Quarterly 49 (5):485-510.score: 48.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  18. H. Rogers (1987). Theory of Recursive Functions and Effective Computability. Mit Press.score: 48.0
  19. Andrés Cordón–Franco & F. Félix Lara–Martín (2012). Local Induction and Provably Total Computable Functions: A Case Study. In. In S. Barry Cooper (ed.), How the World Computes. 440--449.score: 46.0
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  20. M. A. Nielsen, Computable Functions, Quantum Measurements, and Quantum Dynamics.score: 45.0
    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 to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  21. Samuel Alexander (2006). Formulas for Computable and Non-Computable Functions. Rose-Hulman Undergraduate Mathematics Journal 7 (2).score: 45.0
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  22. 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.score: 45.0
    Translate to English
    | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  23. 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.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  24. F. B. Cannonito (1967). Review: Tibor Rado, On a Simple Source for Non-Computable Functions. [REVIEW] Journal of Symbolic Logic 32 (4):524-524.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  25. C. C. Elgot (1963). Review: Robert W. Ritchie, Classes of Predictably Computable Functions. [REVIEW] Journal of Symbolic Logic 28 (3):252-253.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  26. 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.score: 45.0
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  27. 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.score: 45.0
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  28. 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).score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  29. 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.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  30. F. B. Cannonito (1967). Review: T. Rado, On Non-Computable Functions. [REVIEW] Journal of Symbolic Logic 32 (4):524-524.score: 45.0
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  31. 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.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  32. 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.score: 45.0
    Direct download  
     
    My bibliography  
     
    Export citation  
  33. 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.score: 45.0
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  34. Elliott Mendelson (1966). Review: V. A. Uspenskij, (Lekcii o Vycislimyh Funkciah)Lectures on Computable Functions. [REVIEW] Journal of Symbolic Logic 31 (2):263-264.score: 45.0
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  35. R. Zach (2002). RL EPSTEIN and WA CARNIELLI Computability. Computable Functions, Logic, and the Foundations of Mathematics. History and Philosophy of Logic 23 (1):67-69.score: 45.0
     
    My bibliography  
     
    Export citation  
  36. D. Kunkle (2004). Type-2 Computability on Spaces of Integrables Functions. Mathematical Logic Quarterly 50 (4):417.score: 42.0
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  37. C. J. Ash (2000). Computable Structures and the Hyperarithmetical Hierarchy. Elsevier.score: 42.0
    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 (...)
     
    My bibliography  
     
    Export citation  
  38. Helmut Schwichtenberg (2012). Proofs and Computations. Cambridge University Press.score: 40.0
    Driven by the question, 'What is the computational content of a (formal) proof?', this book studies fundamental interactions between proof theory and computability. It provides a unique self-contained text for advanced students and researchers in mathematical logic and computer science. Part I covers basic proof theory, computability and Gödel's theorems. Part II studies and classifies provable recursion in classical systems, from fragments of Peano arithmetic up to Π11-CA0. Ordinal analysis and the (Schwichtenberg-Wainer) subrecursive hierarchies play a central role and are (...)
    Direct download  
     
    My bibliography  
     
    Export citation  
  39. George Boolos, John Burgess, Richard P. & C. Jeffrey (2007). Computability and Logic. Cambridge University Press.score: 39.0
    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  
     
    My bibliography  
     
    Export citation  
  40. Arto Salomaa (1985). Computation and Automata. Cambridge University Press.score: 39.0
    This introduction to certain mathematical topics central to theoretical computer science treats computability and recursive functions, formal languages and automata, computational complexity, and cruptography. The presentation is essentially self-contained with detailed proofs of all statements provided. Although it begins with the basics, it proceeds to some of the most important recent developments in theoretical computer science.
    Direct download  
     
    My bibliography  
     
    Export citation  
  41. S. B. Cooper, Benedikt Löwe & Andrea Sorbi (eds.) (2007). New Computational Paradigms: Changing Conceptions of What is Computable. Springer.score: 39.0
    Logicians and theoretical physicists will also benefit from this book.
    Direct download  
     
    My bibliography  
     
    Export citation  
  42. Raymond Turner (2009). Computable Models. Springer.score: 39.0
    Raymond Turner first provides a logical framework for specification and the design of specification languages, then uses this framework to introduce and study ...
    Direct download  
     
    My bibliography  
     
    Export citation  
  43. 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.score: 39.0
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  44. Vladeta Vučković (1970). Effective Enumerability of Some Families of Partially Recursive Functions Connected With Computable Functionals. Mathematical Logic Quarterly 16 (2):113-121.score: 39.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  45. Stefano Mazzanti (2005). Bounded Iteration and Unary Functions. Mathematical Logic Quarterly 51 (1):89-94.score: 39.0
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  46. Stefano Mazzanti (2013). Iteration on Notation and Unary Functions. Mathematical Logic Quarterly 59 (6):415-434.score: 39.0
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  47. H. E. Rose (1984). Subrecursion: Functions and Hierarchies. Oxford University Press.score: 39.0
    No categories
     
    My bibliography  
     
    Export citation  
  48. Guido Gherardi & Alberto Marcone (2009). How Incomputable Is the Separable Hahn-Banach Theorem? Notre Dame Journal of Formal Logic 50 (4):393-425.score: 36.0
    We determine the computational complexity of the Hahn-Banach Extension Theorem. To do so, we investigate some basic connections between reverse mathematics and computable analysis. In particular, we use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multivalued function Sep and a natural notion of reducibility for multivalued functions, we obtain a computational counterpart of the subsystem of second-order arithmetic WKL0. We study analogies and differences between (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  49. Denis Hirschfeldt, Russell Miller & Sergei Podzorov (2007). Order-Computable Sets. Notre Dame Journal of Formal Logic 48 (3):317-347.score: 36.0
    We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
1 — 50 / 1000