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:
95 found
Search inside:
(import / add options)   Sort by:
1 — 50 / 95
  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. Ayda I. Arruda, Newton C. A. Costdaa & 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.
  4. 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  
  5. 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  
  6. 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  
  7. 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  
  8. 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  
  9. 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  
  10. 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 to0, individual variables, the successor function, the identity relation and operators for disjunction, conjunction, and existential quantification.
    Remove from this list | Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  11. 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  
  12. 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  
  13. Daniel E. Cohen (1987). Computability and Logic. Halsted Press.
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  14. 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  
  15. 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  
  16. 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  
  17. B. J. Copeland, C. Posy & O. Shagrir (eds.) (forthcoming). Computability: Gödel, Turing, Church, and Beyond. MIT Press.
  18. 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.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  19. 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  
  20. 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  
  21. 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  
     
    My bibliography  
     
    Export citation  
  22. Martin Davies, Ron Segal & Elaine Weyuker (1994). Computability, Complexity and Languages. Academic Press.
    Remove from this list |
    Translate to English
    |
     
    My bibliography  
     
    Export citation  
  23. 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  
  24. 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  
     
    My bibliography  
     
    Export citation  
  25. 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  
  26. 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  
  27. Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. [REVIEW] Minds and Machines 18 (3):349-355.
  28. 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  
  29. 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  
  30. Branden Fitelson, Comments on Presting's “Computability and Newcomb's Problem”.
    • What’s essential to Newcomb’s problem? 1. You must choose between two particular acts: A1 = you take just the opaque box; A2 = you take both boxes, where the two states of nature are: S 1 = there’s $1M in the opaque box, S2 = there’s $0 in the opaque box.
    Remove from this list |
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  31. Melvin Fitting (1987). Computability Theory, Semantics, and Logic Programming. Clarendon Press.
    This book describes computability theory and provides an extensive treatment of data structures and program correctness. It makes accessible some of the author's work on generalized recursion theory, particularly the material on the logic programming language PROLOG, which is currently of great interest. Fitting considers the relation of PROLOG logic programming to the LISP type of language.
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  32. Nir Fresco (2011). Concrete Digital Computation: What Does It Take for a Physical System to Compute? [REVIEW] Journal of Logic, Language and Information 20 (4):513-537.
    This paper deals with the question: what are the key requirements for a physical system to perform digital computation? Time and again cognitive scientists are quick to employ the notion of computation simpliciter when asserting basically that cognitive activities are computational. They employ this notion as if there was or is a consensus on just what it takes for a physical system to perform computation, and in particular digital computation. Some cognitive scientists in referring to digital computation simply adhere to (...)
    Remove from this list | Direct download (15 more)  
     
    My bibliography  
     
    Export citation  
  33. D. M. Gabbay & D. H. J. de Jongh (1974). A Sequence of Decidable Finitely Axiomatizable Intermediate Logics with the Disjunction Property. Journal of Symbolic Logic 39 (1):67-78.
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  34. Giangiacomo Gerla (1989). Turing L -Machines and Recursive Computability for L -Maps. Studia Logica 48 (2):179 - 192.
    We propose the notion of partial recursiveness and strong partial recursiveness for fuzzy maps. We prove that a fuzzy map f is partial recursive if and only if it is computable by a Turing fuzzy machine and that f is strongly partial recursive and deterministic if and only if it is computable via a deterministic Turing fuzzy machine. This gives a simple and manageable tool to investigate about the properties of the fuzzy machines.
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  35. Robert Geroch & James B. Hartle (1986). Computability and Physical Theories. Foundations of Physics 16 (6):533-550.
    The familiar theories of physics have the feature that the application of the theory to make predictions in specific circumstances can be done by means of an algorithm. We propose a more precise formulation of this feature—one based on the issue of whether or not the physically measurable numbers predicted by the theory are computable in the mathematical sense. Applying this formulation to one approach to a quantum theory of gravity, there are found indications that there may exist no such (...)
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  36. Guido Gherardi (2011). Alan Turing and the Foundations of Computable Analysis. Bulletin of Symbolic Logic 17 (3):394-430.
    We investigate Turing's contributions to computability theory for real numbers and real functions presented in [22, 24, 26]. In particular, it is shown how two fundamental approaches to computable analysis, the so-called ‘Type-2 Theory of Effectivity' (TTE) and the ‘realRAM machine' model, have their foundations in Turing's work, in spite of the two incompatible notions of computability they involve. It is also shown, by contrast, how the modern conceptual tools provided by these two paradigms allow a systematic interpretation of Turing's (...)
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  37. Edward R. Griffor (ed.) (1999). Handbook of Computability Theory. Elsevier.
    The chapters of this volume all have their own level of presentation. The topics have been chosen based on the active research interest associated with them. Since the interest in some topics is older than that in others, some presentations contain fundamental definitions and basic results while others relate very little of the elementary theory behind them and aim directly toward an exposition of advanced results. Presentations of the latter sort are in some cases restricted to a short survey of (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  38. Jeremy Gwiazda (2011). Infinitism, Completability, and Computability: Reply to Peijnenburg. Mind 119 (476):1123-1124.
    In ‘Infinitism Regained’, Jeanne Peijnenburg argues for a version of infinitism wherein ‘beliefs may be justified by an infinite chain of reasons that can be actually completed’. I argue that Peijnenburg has not successfully argued for this claim, but rather has shown that certain infinite series can be computed.
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  39. Robert F. Hadley (2008). Consistency, Turing Computability and Gödel's First Incompleteness Theorem. Minds and Machines 18 (1):1-15.
    It is well understood and appreciated that Gödel’s Incompleteness Theorems apply to sufficiently strong, formal deductive systems. In particular, the theorems apply to systems which are adequate for conventional number theory. Less well known is that there exist algorithms which can be applied to such a system to generate a gödel-sentence for that system. Although the generation of a sentence is not equivalent to proving its truth, the present paper argues that the existence of these algorithms, when conjoined with Gödel’s (...)
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  40. Valentina S. Harizanov (2002). Computability-Theoretic Complexity of Countable Structures. Bulletin of Symbolic Logic 8 (4):457-477.
    Remove from this list | Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  41. Shawn Hedman (2004). A First Course in Logic: An Introduction to Model Theory, Proof Theory, Computability, and Complexity. Oxford University Press.
    The ability to reason and think in a logical manner forms the basis of learning for most mathematics, computer science, philosophy and logic students. Based on the author's teaching notes at the University of Maryland and aimed at a broad audience, this text covers the fundamental topics in classical logic in an extremely clear, thorough and accurate style that is accessible to all the above. Covering propositional logic, first-order logic, and second-order logic, as well as proof theory, computability theory, and (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  42. Wilfrid Hodges (2009). Set Theory, Model Theory, and Computability Theory. In Leila Haaparanta (ed.), The Development of Modern Logic. Oxford University Press. 471.
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  43. Wilfrid Hodges (2008). Main Trends in Mathematical Logic After the 1930s : Set Theory, Model Theory, and Computability Theory. In Leila Haaparanta (ed.), The Development of Modern Logic. Oxford University Press.
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  44. Mark Hogarth (1996). Predictability, Computability and Spacetime. Dissertation, Cambridge University
    Remove from this list |
    Translate to English
    |
     
    My bibliography  
     
    Export citation  
  45. Mark Hogarth (1994). Non-Turing Computers and Non-Turing Computability. Psa 1994:126--138.
    A true Turing machine (TM) requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime (the spacetime of common sense), but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are similar ("close") to (...)
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  46. Tamara Horowitz (forthcoming). Computability as a Physical Modality. Unpublished Ms Held in the Casimir Lewy Library, Cambridge.
    Remove from this list |
    Translate to English
    |
     
    My bibliography  
     
    Export citation  
  47. Abir Igamberdiev (ed.) (2011). Physics and Logic of Life. Nova Science Pub..
    This book discusses the basic foundations of theoretical biology. Contrary to the objects of theoretical physics, the biological object contains a kind of ontological duality and refers to a fundamental wholeness of a living system. The rational interpretation of wholeness is considered by the author as a true basis for fundamental principles of development of theoretical biology and for understanding its link to physics, to psychology, and to semiotics. The rational holistic approach in application to theoretical biology can be substantiated (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  48. Neil Immerman, Computability and Complexity. Stanford Encyclopedia of Philosophy.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  49. Giorgi Japaridze (2010). Towards Applied Theories Based on Computability Logic. Journal of Symbolic Logic 75 (2):565-601.
    Computability logic (CL) is a recently launched program for redeveloping logic as a formal theory of computability, as opposed to the formal theory of truth that logic has more traditionally been. Formulas in it represent computational problems, "truth" means existence of an algorithmic solution, and proofs encode such solutions. Within the line of research devoted to finding axiomatizations for ever more expressive fragments of CL, the present paper introduces a new deductive system CL12 and proves its soundness and completeness with (...)
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  50. N. D. Jones (1997). Computability and Complexity: From a Programming Perspective Vol. 21. Mit Press.
    This makes his book especially valuable." -- Yuri Gurevich, Professor of Computer Science, University of Michigan Computability and complexity theory should be of central concern to practitioners as well as theorists.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
1 — 50 / 95