This category needs an editor. We encourage you to help if you are qualified.
Volunteer, or read more about what this involves.
Related categories
Siblings:
176 found
Search inside:
(import / add options)   Sort by:
1 — 50 / 176
  1. Samuel Alexander (2011). A Paradox Related to the Turing Test. The Reasoner 5 (6):90-90.
  2. Samuel Alexander (2006). Formulas for Computable and Non-Computable Functions. Rose-Hulman Undergraduate Mathematics Journal 7 (2).
    Remove from this list |
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  3. Klaus Ambos-Spies, Arnold Beckmann, Samuel R. Buss & Benedikt Löwe (2012). Computability in Europe 2009. Annals of Pure and Applied Logic 163 (5):483-484.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  4. Toshiyasu Arai (2015). Predicatively Computable Functions on Sets. Archive for Mathematical Logic 54 (3-4):471-485.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  5. Ayda I. Arruda, R. Chuaqui & Newton C. A. da Costa (1977). Non-Classical Logics, Model Theory, and Computability Proceedings of the Third Latin-American Symposium on Mathematical Logic, Campinas, Brazil, July 11-17, 1976. [REVIEW]
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  6. Ayda I. Arruda, Newton C. A. Costa & R. Chuaqui (eds.) (1977). Non-Classical Logics, Model Theory, and Computability: Proceedings of the Third Latin-American Symposium on Mathematical Logic, Campinas, Brazil, July 11-17, 1976. [REVIEW] Sale Distributors for the U.S.A. And Canada, Elsevier/North-Holland.
  7. Jeremy Avigad, Computability and Convergence.
    For most of its history, mathematics was fairly constructive: • Euclidean geometry was based on geometric construction. • Algebra sought explicit solutions to equations. Analysis, probability, etc. were focused on calculations. Nineteenth century developments in analysis challenged this view. A sequence (an) in a metric space is said Cauchy if for every ε > 0, there is an m such that for every n, n ≥ m, d (a n , a n ) < ε.
    Remove from this list |
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  8. Arnon Avron (2005). A Non-Deterministic View on Non-Classical Negations. Studia Logica 80 (2-3):159 - 194.
    We investigate two large families of logics, differing from each other by the treatment of negation. The logics in one of them are obtained from the positive fragment of classical logic (with or without a propositional constant ff for “the false”) by adding various standard Gentzen-type rules for negation. The logics in the other family are similarly obtained from LJ+, the positive fragment of intuitionistic logic (again, with or without ff). For all the systems, we provide simple semantics which is (...)
    Remove from this list | Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  9. Steve Awodey, Lars Birkedal & Dana Scott, Local Realizability Toposes and a Modal Logic for Computability.
    This work is a step toward the development of a logic for types and computation that includes not only the usual spaces of mathematics and constructions, but also spaces from logic and domain theory. Using realizability, we investigate a configuration of three toposes that we regard as describing a notion of relative computability. Attention is focussed on a certain local map of toposes, which we first study axiomatically, and then by deriving a modal calculus as its internal logic. The resulting (...)
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Paul Axt (1961). Note on the 3‐Recursive Functions. Mathematical Logic Quarterly 7 (7‐10):97-98.
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  11. Verónica Becher (2005). Logic, Computability, and Randomness. Bulletin of Symbolic Logic 11 (4):557-557.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  12. Lev D. Beklemishev (2003). On the Induction Schema for Decidable Predicates. Journal of Symbolic Logic 68 (1):17-34.
    We study the fragment of Peano arithmetic formalizing the induction principle for the class of decidable predicates, $I\Delta_1$ . We show that $I\Delta_1$ is independent from the set of all true arithmetical $\Pi_2-sentences$ . Moreover, we establish the connections between this theory and some classes of oracle computable functions with restrictions on the allowed number of queries. We also obtain some conservation and independence results for parameter free and inference rule forms of $\Delta_1-induction$ . An open problem formulated by J. (...)
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  13. John W. Berry (1974). N-Ary Almost Recursive Functions. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 20 (34-36):551-559.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  14. Richard Bird (1975). Non Recursive Functionals. Mathematical Logic Quarterly 21 (1):41-46.
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  15. Patrick Blackburn & Maarten Marx (2002). Remarks on Gregory's “Actually” Operator. Journal of Philosophical Logic 31 (3):281-288.
    In this note we show that the classical modal technology of Sahlqvist formulas gives quick proofs of the completeness theorems in [8] (D. Gregory, Completeness and decidability results for some propositional modal logics containing "actually" operators, Journal of Philosophical Logic 30(1): 57-78, 2001) and vastly generalizes them. Moreover, as a corollary, interpolation theorems for the logics considered in [8] are obtained. We then compare Gregory's modal language enriched with an "actually" operator with the work of Arthur Prior now known under (...)
    Remove from this list | Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  16. 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, a (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  17. E. Börger (1989). Computability, Complexity, Logic. New York, N.Y., U.S.A.Elsevier Science Pub. Co..
    The theme of this book is formed by a pair of concepts: the concept of formal language as carrier of the precise expression of meaning, facts and problems, and the concept of algorithm or calculus, i.e. a formally operating procedure for the solution of precisely described questions and problems. The book is a unified introduction to the modern theory of these concepts, to the way in which they developed first in mathematical logic and computability theory and later in automata theory, (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  18. Fabio Boschetti & Randall Gray (2007). Emergence and Computability. Emergence: Complexity and Organization 9.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  19. Volker Bosserhoff (2007). Computability of Solutions of Operator Equations. Mathematical Logic Quarterly 53 (4):326-344.
    We study operator equations within the Turing machine based framework for computability in analysis. Is there an algorithm that maps pairs to solutions of Tx = u ? Here we consider the case when T is a bounded linear mapping between Hilbert spaces. We are in particular interested in computing the generalized inverse T†u, which is the standard concept of solution in the theory of inverse problems. Typically, T† is discontinuous and hence no computable mapping. However, we will use effective (...)
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  20. Vasco Brattka (2008). Borel Complexity and Computability of the Hahn–Banach Theorem. Archive for Mathematical Logic 46 (7-8):547-564.
    The classical Hahn–Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling the classical proof of the (...)
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  21. 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 functions and corresponding complete functions. (...)
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  22. James Cain (1999). The Theory of Computability Developed in Terms of Satisfaction. Notre Dame Journal of Formal Logic 40 (4):515-532.
    The notion of computability is developed through the study of the behavior of a set of languages interpreted over the natural numbers which contain their own fully defined satisfaction predicate and whose only other vocabulary is limited to "0", individual variables, the successor function, the identity relation and operators for disjunction, conjunction, and existential quantification.
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  23. Cristian Calude (2001). Real Numbers: From Computable to Random. Studia Philosophica 1.
    A real is computable if it is the limit of a computable, increasing, computably converging sequence of rational...
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  24. Cristian Calude, M. J. Dinneen & Silviu Sburlan (2001). Combinatorics, Computability and Logic Proceedings of the Third International Conference on Combinatorics, Computability and Logic. Monograph Collection (Matt - Pseudo).
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  25. 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 et al. (...)
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  26. Douglas Cenzer & Jeffrey B. Remmel (2006). Complexity, Decidability and Completeness. Journal of Symbolic Logic 71 (2):399 - 424.
    We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...)
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  27. Jennifer Chubb, Jeffry L. Hirst & Timothy H. McNicholl (2009). Reverse Mathematics, Computability, and Partitions of Trees. Journal of Symbolic Logic 74 (1):201-215.
    We examine the reverse mathematics and computability theory of a form of Ramsey's theorem in which the linear n-tuples of a binary tree are colored.
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  28. Daniel E. Cohen (1987). Computability and Logic. Halsted Press.
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  29. Roy T. Cook (2014). B. Jack Copeland, Carl J. Posy, and Oron Shagrir, Eds, Computability: Turing, Gödel, Church, and Beyond. Cambridge, Mass.: MIT Press, 2013. ISBN 978-0-262-01899-9. Pp. X + 362. [REVIEW] Philosophia Mathematica 22 (3):412-413.
  30. S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.) (1996). Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press.
    The fundamental ideas concerning computation and recursion naturally find their place at the interface between logic and theoretical computer science. The contributions in this book, by leaders in the field, provide a picture of current ideas and methods in the ongoing investigations into the pure mathematical foundations of computability theory. The topics range over computable functions, enumerable sets, degree structures, complexity, subrecursiveness, domains and inductive inference. A number of the articles contain introductory and background material which it is hoped will (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  31. S. B. Cooper & Andrea Sorbi (eds.) (2011). Computability in Context: Computation and Logic in the Real World. World Scientific.
    Recent new paradigms of computation, based on biological and physical models, address in a radically new way questions of efficiency and challenge assumptions ...
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  32. S. B. Cooper & J. K. Truss (eds.) (1999). Models and Computability: Invited Papers From Logic Colloquium '97, European Meeting of the Association for Symbolic Logic, Leeds, July 1997. Cambridge University Press.
    Together, Models and Computability and its sister volume Sets and Proofs will provide readers with a comprehensive guide to the current state of mathematical logic. All the authors are leaders in their fields and are drawn from the invited speakers at 'Logic Colloquium '97' (the major international meeting of the Association of Symbolic Logic). It is expected that the breadth and timeliness of these two volumes will prove an invaluable and unique resource for specialists, post-graduate researchers, and the informed and (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  33. B. J. Copeland, C. Posy & O. Shagrir (eds.) (forthcoming). Computability: Gödel, Turing, Church, and Beyond. MIT Press.
  34. B. Jack Copeland & Diane Proudfoot (2010). Deviant Encodings and Turing's Analysis of Computability. Studies in History and Philosophy of Science Part A 41 (3):247-252.
    Turing’s analysis of computability has recently been challenged; it is claimed that it is circular to analyse the intuitive concept of numerical computability in terms of the Turing machine. This claim threatens the view, canonical in mathematics and cognitive science, that the concept of a systematic procedure or algorithm is to be explicated by reference to the capacities of Turing machines. We defend Turing’s analysis against the challenge of ‘deviant encodings’.Keywords: Systematic procedure; Turing machine; Church–Turing thesis; Deviant encoding; Acceptable encoding; (...)
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  35. Barbara F. Csima & Robert I. Soare (2006). Computability Results Used in Differential Geometry. Journal of Symbolic Logic 71 (4):1394 - 1410.
    Topologists Nabutovsky and Weinberger discovered how to embed computably enumerable (c.e.) sets into the geometry of Riemannian metrics modulo diffeomorphisms. They used the complexity of the settling times of the c.e. sets to exhibit a much greater complexity of the depth and density of local minima for the diameter function than previously imagined. Their results depended on the existence of certain sequences of c.e. sets, constructed at their request by Csima and Soare, whose settling times had the necessary dominating properties. (...)
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  36. Michael E. Cuffaro (forthcoming). How-Possibly Explanations in Quantum Computer Science. Philosophy of Science.
    A primary goal of quantum computer science is to find an explanation for the fact that quantum computers are more powerful than classical computers. In this paper I argue that to answer this question is to compare algorithmic processes of various kinds, and in so doing to describe the possibility spaces associated with these processes. By doing this we explain how it is possible for one process to outperform its rival. Further, in this and similar examples little is gained in (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  37. 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). Dr Cutland (...)
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  38. F. Dahlgren (2004). Computability and Continuity in Computable Metric Partial Algebras Equipped with Computability Structures. Mathematical Logic Quarterly 50 (4):486.
    In this paper we give an axiomatisation of the concept of a computability structure with partial sequences on a many-sorted metric partial algebra, thus extending the axiomatisation given by Pour-El and Richards in [9] for Banach spaces. We show that every Banach-Mazur computable partial function from an effectively separable computable metric partial Σ-algebra A to a computable metric partial Σ-algebra B must be continuous, and conversely, that every effectively continuous partial function with semidecidable domain and which preserves the computability of (...)
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  39. Martin Davies, Ron Segal & Elaine Weyuker (1994). Computability, Complexity and Languages. Academic Press.
    Remove from this list |
    Translate to English
    |
     
    My bibliography  
     
    Export citation  
  40. Martin Davis (1990). Book Review: Melvin Fitting. Computability Theory, Semantics, and Logic Programming. [REVIEW] Notre Dame Journal of Formal Logic 31 (3):485-486.
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  41. 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.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  42. J. C. E. Dekker & E. Ellentuck (1974). Recursion Relative to Regressive Functions. Annals of Mathematical Logic 6 (3-4):231-257.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  43. Nachum Dershowitz & Yuri Gurevich (2008). A Natural Axiomatization of Computability and Proof of Church's Thesis. Bulletin of Symbolic Logic 14 (3):299-350.
    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 proof of Church's (...)
    Remove from this list | Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  44. Rod Downey (1998). Computability Theory and Linear Orders. In I͡Uriĭ Leonidovich Ershov (ed.), Handbook of Recursive Mathematics. Elsevier. 138--823.
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  45. Rodney G. Downey, Sergei S. Goncharov, Asher M. Kach, Julia F. Knight, Oleg V. Kudinov, Alexander G. Melnikov & Daniel Turetsky (2010). Decidability and Computability of Certain Torsion-Free Abelian Groups. Notre Dame Journal of Formal Logic 51 (1):85-96.
    We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  46. Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. [REVIEW] Minds and Machines 18 (3):349-355.
  47. Herbert B. Enderton (2011). Computability Theory: An Introduction to Recursion Theory. Academic Press.
    Machine generated contents note: 1. The Computability Concept;2. General Recursive Functions;3. Programs and Machines;4. Recursive Enumerability;5. Connections to Logic;6. Degrees of Unsolvability;7. Polynomial-Time Computability;Appendix: Mathspeak;Appendix: Countability;Appendix: Decadic Notation;.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  48. Richard L. Epstein & Walter A. Carnielli (1989). Computability Computable Functions, Logic, and the Foundations of Mathematics. Monograph Collection (Matt - Pseudo).
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  49. Jens Erik Fenstad & Peter G. Hinman (eds.) (1974). Generalized Recursion Theory. New York,American Elsevier Pub. Co..
    Provability, Computability and Reflection.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  50. Fernando Ferreira (ed.) (2010). Programs, Proofs, Processes: 6th Conference on Computability in Europe, Cie, 2010, Ponta Delgada, Azores, Portugal, June 30-July 4, 2010 ; Proceedings. [REVIEW] Springer.
    The LNCS series reports state-of-the-art results in computer science research, development, and education, at a high level and in both printed and electronic form.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
1 — 50 / 176