The Wayback Machine - https://web.archive.org/web/20170311155603/https://philpapers.org/browse/computability/
This category needs an editor. We encourage you to help if you are qualified.
Volunteer, or read more about what this involves.
Related categories

411 found
Order:
1 — 50 / 411
  1. Chapter Twelve Growing Minds, Computability, and the Potentially Infinite Darren Abramson.Darren Abramson - 2007 - In Soraj Hongladarom (ed.), Computing and Philosophy in Asia. Cambridge Scholars Press. pp. 179.
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  2. A Paradox Related to the Turing Test.Samuel Alexander - 2011 - The Reasoner 5 (6):90-90.
  3. Formulas for Computable and Non-Computable Functions.Samuel Alexander - 2006 - Rose-Hulman Undergraduate Mathematics Journal 7 (2).
    Remove from this list  
    Translate
      Direct download  
     
    Export citation  
     
    My bibliography  
  4. Computability in Europe 2009.Klaus Ambos-Spies, Arnold Beckmann, Samuel R. Buss & Benedikt Löwe - 2012 - Annals of Pure and Applied Logic 163 (5):483-484.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  5. Approximation to a Decision Procedure for the Halting Problem.Michael Anderson - 1968 - Notre Dame Journal of Formal Logic 9 (4):305-312.
  6. Predicatively Computable Functions on Sets.Toshiyasu Arai - 2015 - Archive for Mathematical Logic 54 (3-4):471-485.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  7. The Changing Practices of Proof in Mathematics.Andrew Arana - forthcoming - Metascience:1-5.
  8. Review of Computability: Turing, Gödel, Church, and Beyond. [REVIEW]Andrew Arana - 2015 - Notre Dame Philosophical Reviews 3 (20).
    A review of Computability: Turing, Gödel, Church, and Beyond by Copeland, Posy and Shagrir.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography  
  9. Possible M-Diagrams of Models of Arithmetic.Andrew Arana - 2005 - In Stephen Simpson (ed.), Reverse Mathematics 2001.
    In this paper I begin by extending two results of Solovay; the first characterizes the possible Turing degrees of models of True Arithmetic (TA), the complete first-order theory of the standard model of PA, while the second characterizes the possible Turing degrees of arbitrary completions of P. I extend these two results to characterize the possible Turing degrees of m-diagrams of models of TA and of arbitrary complete extensions of PA. I next give a construction showing that the conditions Solovay (...)
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  10. Non-Classical Logics, Model Theory, and Computability Proceedings of the Third Latin-American Symposium on Mathematical Logic, Campinas, Brazil, July 11-17, 1976. [REVIEW]Ayda I. Arruda, R. Chuaqui & Newton C. A. da Costa - 1977 -
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  11. Non-Classical Logics, Model Theory, and Computability: Proceedings of the Third Latin-American Symposium on Mathematical Logic, Campinas, Brazil, July 11-17, 1976. [REVIEW]Ayda I. Arruda, Newton C. A. Costa & R. Chuaqui (eds.) - 1977 - Sale Distributors for the U.S.A. And Canada, Elsevier/North-Holland.
  12. Recursion Theory and Complexity: Proceedings of the Kazan '97 Workshop, Kazan, Russia, July 14-19, 1997.M. M. Arslanov & Steffen Lempp (eds.) - 1999 - W. De Gruyter.
  13. Computability and Convergence.Jeremy Avigad - unknown -
    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
      Direct download  
     
    Export citation  
     
    My bibliography  
  14. Local Stability of Ergodic Averages.Jeremy Avigad - unknown -
    We consider the extent to which one can compute bounds on the rate of convergence of a sequence of ergodic averages. It is not difficult to construct an example of a computable Lebesgue measure preserving transformation of [0, 1] and a characteristic function f = χA such that the ergodic averages Anf do not converge to a computable element of L2([0, 1]). In particular, there is no computable bound on the rate of convergence for that sequence. On the other hand, (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  15. Computability and Analysis: The Legacy of Alan Turing.Jeremy Avigad & Vasco Brattka - unknown -
    We discuss the legacy of Alan Turing and his impact on computability and analysis.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  16. Algorithmic Randomness, Reverse Mathematics, and the Dominated Convergence Theorem.Jeremy Avigad, Edward T. Dean & Jason Rute - 2012 - Annals of Pure and Applied Logic 163 (12):1854-1864.
    We analyze the pointwise convergence of a sequence of computable elements of L1 in terms of algorithmic randomness. We consider two ways of expressing the dominated convergence theorem and show that, over the base theory RCA0, each is equivalent to the assertion that every Gδ subset of Cantor space with positive measure has an element. This last statement is, in turn, equivalent to weak weak Königʼs lemma relativized to the Turing jump of any set. It is also equivalent to the (...)
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  17. A Non-Deterministic View on Non-Classical Negations.Arnon Avron - 2005 - 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 (5 more)  
     
    Export citation  
     
    My bibliography  
  18. Local Realizability Toposes and a Modal Logic for Computability.Steve Awodey, Lars Birkedal & Dana Scott - unknown -
    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)  
     
    Export citation  
     
    My bibliography  
  19. Iteration of Primitive Recursion.Paul Axt - 1965 - Mathematical Logic Quarterly 11 (3):253-255.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  20. Note on the 3‐Recursive Functions.Paul Axt - 1961 - Mathematical Logic Quarterly 7 (7‐10):97-98.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  21. Note on the 3-Recursive Functions.Paul Axt - 1961 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 7 (7-10):97-98.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  22. Evolutionary Scenarios for the Emergence of Recursion.Lluís Barceló-Coblijn - forthcoming - Theoria Et Historia Scientiarum 9:171-199.
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  23. Algorithmic Randomness and Measures of Complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography   1 citation  
  24. Algorithmic Randomness of Continuous Functions.George Barmpalias, Paul Brodhead, Douglas Cenzer, Jeffrey B. Remmel & Rebecca Weber - 2008 - Archive for Mathematical Logic 46 (7-8):533-546.
    We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}$ of continuous functions on ${2^{\mathbb N}}$ . A probability measure is given and a version of the Martin-Löf test for randomness is defined. Random ${\Delta^0_2}$ continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any ${y \in 2^{\mathbb N}}$ , (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  25. Two Constructive Embedding‐Extension Theorems with Applications to Continuity Principles and to Banach‐Mazur Computability.Andrej Bauer & Alex Simpson - 2004 - Mathematical Logic Quarterly 50 (4‐5):351-369.
    We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non-compact CSM. Both results rely on having careful (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  26. Logic, Computability, and Randomness.Verónica Becher - 2005 - Bulletin of Symbolic Logic 11 (4):557-557.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  27. Conference on Computability, Complexity and Randomness.Verónica Becher, C. T. Chong, Rod Downey, Noam Greenberg, Antonin Kucera, Bjørn Kjos-Hanssen, Steffen Lempp, Antonio Montalbán, Jan Reimann & Stephen Simpson - 2008 - Bulletin of Symbolic Logic 14 (4):548-549.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  28. On the Induction Schema for Decidable Predicates.Lev D. Beklemishev - 2003 - 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 (8 more)  
     
    Export citation  
     
    My bibliography  
  29. On the Correct Definition of Randomness.Paul Benioff - 1978 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1978:63 - 78.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography  
  30. N-Ary Almost Recursive Functions.John W. Berry - 1974 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 20 (34-36):551-559.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  31. Constructive Equivalence Relations on Computable Probability Measures.Laurent Bienvenu & Wolfgang Merkle - 2009 - Annals of Pure and Applied Logic 160 (3):238-254.
    A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences. In what follows, (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  32. Randomness and Lowness Notions Via Open Covers.Laurent Bienvenu & Joseph S. Miller - 2012 - Annals of Pure and Applied Logic 163 (5):506-518.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  33. Non Recursive Functionals.Richard Bird - 1975 - Mathematical Logic Quarterly 21 (1):41-46.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  34. Remarks on Gregory's “Actually” Operator.Patrick Blackburn & Maarten Marx - 2002 - 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)  
     
    Export citation  
     
    My bibliography   5 citations  
  35. Computability and Logic.S. Boolos George, P. Burgess John & C. Jeffrey Richard - 2007 - 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. This 2007 fifth edition has been thoroughly revised by John Burgess. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a (...)
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  36. Computability and Logic.George S. Boolos, John P. Burgess & Richard C. Jeffrey - 2007 - 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. This 2007 fifth edition has been thoroughly revised by John Burgess. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a (...)
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  37. Computability and Logic.George Boolos, John Burgess, Richard P. & C. Jeffrey - 2007 - 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  
     
    Export citation  
     
    My bibliography   90 citations  
  38. Computability, Complexity, Logic.E. Börger - 1989 - New York: 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  
     
    Export citation  
     
    My bibliography   4 citations  
  39. Emergence and Computability.Fabio Boschetti & Randall Gray - 2007 - Emergence: Complexity and Organization 9.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography   3 citations  
  40. Computability of Solutions of Operator Equations.Volker Bosserhoff - 2007 - 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 (3 more)  
     
    Export citation  
     
    My bibliography  
  41. A Computable Version of Banach's Inverse Mapping Theorem.Vasco Brattka - 2009 - Annals of Pure and Applied Logic 157 (2):85-96.
    Given a program of a linear bounded and bijective operator T, does there exist a program for the inverse operator T−1? And if this is the case, does there exist a general algorithm to transfer a program of T into a program of T−1? This is the inversion problem for computable linear operators on Banach spaces in its non-uniform and uniform formulation, respectively. We study this problem from the point of view of computable analysis which is the Turing machine based (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  42. Borel Complexity and Computability of the Hahn–Banach Theorem.Vasco Brattka - 2008 - 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)  
     
    Export citation  
     
    My bibliography   3 citations  
  43. Effective Borel Measurability and Reducibility of Functions.Vasco Brattka - 2005 - 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)  
     
    Export citation  
     
    My bibliography   12 citations  
  44. Computability of Finite-Dimensional Linear Subspaces and Best Approximation.Vasco Brattka & Ruth Dillhage - 2010 - Annals of Pure and Applied Logic 162 (3):182-193.
    We discuss computability properties of the set of elements of best approximation of some point xX by elements of GX in computable Banach spaces X. It turns out that for a general closed set G, given by its distance function, we can only obtain negative information about as a closed set. In the case that G is finite-dimensional, one can compute negative information on as a compact set. This implies that one can compute the point in whenever it is uniquely (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  45. A Study on Universal Functions.Bruno Buchberger - 1972 - Institut für Numerische Mathematik Und Elektronische Informationsverarbeitung, Universität Innsbruck.
    Remove from this list  
     
    Export citation  
     
    My bibliography  
  46. Computability in Europe 2011.Sam Buss, Benedikt Löwe, Dag Normann & Ivan Soskov - 2013 - Annals of Pure and Applied Logic 164 (5):509-510.
  47. The Theory of Computability Developed in Terms of Satisfaction.James Cain - 1999 - 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)  
     
    Export citation  
     
    My bibliography  
  48. Real Numbers: From Computable to Random.Cristian Calude - 2001 - 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  
     
    Export citation  
     
    My bibliography  
  49. Topological Size of Sets of Partial Recursive Functions.Cristian Calude - 1982 - Mathematical Logic Quarterly 28 (27‐32):455-462.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  50. Combinatorics, Computability and Logic Proceedings of the Third International Conference on Combinatorics, Computability and Logic.Cristian Calude, M. J. Dinneen & Silviu Sburlan - 2001 -
    Remove from this list  
     
    Export citation  
     
    My bibliography  
1 — 50 / 411