About this topic
Summary When a mathematical theory is decidable we are able to check in some mechanistic fashion whether some well-formed statement in the language of the theory is a theorem (lemma, corollary, etc.). More precisely, a theory is decidable when the set of theorems (lemmas, corollaries, etc.) is recursive. A theory is undecidable, naturally, when this is not the case. Given that completeness and decidability go hand in hand, when we have found an incomplete theory we have also found an undecidable theory. So, Gödel's incompleteness results yield the further result of showing these incomplete theories also have the feature of not being able to check whether the set of theorems is recursive.
Key works Church (1936a), Gödel (Collected Works), Turing, Mostowski, and Robinson (1953), Davis (1977)
Related categories

13 found
Order:
  1. Solvable Cases of the Decision Problem.W. Ackermann - 1954 - Amsterdam: North-Holland Pub. Co..
  2. On First-Order Theories with Provability Operator.Sergei Artëmov & Franco Montagna - 1994 - Journal of Symbolic Logic 59 (4):1139-1153.
    In this paper the modal operator "x is provable in Peano Arithmetic" is incorporated into first-order theories. A provability extension of a theory is defined. Presburger Arithmetic of addition, Skolem Arithmetic of multiplication, and some first order theories of partial consistency statements are shown to remain decidable after natural provability extensions. It is also shown that natural provability extensions of a decidable theory may be undecidable.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  3. The Unprovability in Intuitionistic Formal Systems of the Continuity of Effective Operations on the Reals.Michael Beeson - 1976 - Journal of Symbolic Logic 41 (1):18-24.
  4. Incompleteness in a General Setting (Vol 13, Pg 21, 2007).John Bell - 2008 - Bulletin of Symbolic Logic 14 (1):21 - 30.
    Full proofs of the Gödel incompleteness theorems are highly intricate affairs. Much of the intricacy lies in the details of setting up and checking the properties of a coding system representing the syntax of an object language (typically, that of arithmetic) within that same language. These details are seldom illuminating and tend to obscure the core of the argument. For this reason a number of efforts have been made to present the essentials of the proofs of Gödel’s theorems without getting (...)
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  5. Corrigendum to “Incompleteness in a General Setting”.John L. Bell - 2008 - Bulletin of Symbolic Logic 14 (1):122-122.
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  6. The Gödel Paradox and Wittgenstein's Reasons.Francesco Berto - 2009 - Philosophia Mathematica 17 (2):208-219.
    An interpretation of Wittgenstein’s much criticized remarks on Gödel’s First Incompleteness Theorem is provided in the light of paraconsistent arithmetic: in taking Gödel’s proof as a paradoxical derivation, Wittgenstein was drawing the consequences of his deliberate rejection of the standard distinction between theory and metatheory. The reasoning behind the proof of the truth of the Gödel sentence is then performed within the formal system itself, which turns out to be inconsistent. It is shown that the features of paraconsistent arithmetics match (...)
    Remove from this list   Direct download (11 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  7. What Does Gödel's Second Theorem Say.Michael Detlefsen - 2001 - Philosophia Mathematica 9 (1):37-71.
    We consider a seemingly popular justification (we call it the Re-flexivity Defense) for the third derivability condition of the Hilbert-Bernays-Löb generalization of Godel's Second Incompleteness Theorem (G2). We argue that (i) in certain settings (rouglily, those where the representing theory of an arithmetization is allowed to be a proper subtheory of the represented theory), use of the Reflexivity Defense to justify the tliird condition induces a fourth condition, and that (ii) the justification of this fourth condition faces serious obstacles. We (...)
    Remove from this list   Direct download (9 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  8. Unbounded Operators and the Incompleteness of Quantum Mechanics.Adrian Heathcote - 1990 - Philosophy of Science 57 (3):523-534.
    A proof is presented that a form of incompleteness in Quantum Mechanics follows directly from the use of unbounded operators. It is then shown that the problems that arise for such operators are not connected to the non- commutativity of many pairs of operators in Quantum Mechanics and hence are an additional source of incompleteness to that which allegedly flows from the..
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  9. Reflections on Concrete Incompleteness.G. Longo - 2011 - Philosophia Mathematica 19 (3):255-280.
    How do we prove true but unprovable propositions? Gödel produced a statement whose undecidability derives from its ad hoc construction. Concrete or mathematical incompleteness results are interesting unprovable statements of formal arithmetic. We point out where exactly the unprovability lies in the ordinary ‘mathematical’ proofs of two interesting formally unprovable propositions, the Kruskal-Friedman theorem on trees and Girard's normalization theorem in type theory. Their validity is based on robust cognitive performances, which ground mathematics in our relation to space and time, (...)
    Remove from this list   Direct download (9 more)  
     
    Export citation  
     
    My bibliography  
  10. Three Concepts of Decidability of General Subsets of Uncountable Spaces.Matthew W. Parker - 2006 - Theoretical Computer Science 351 (1):2-13.
    There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, in: R.S. (...)
    Remove from this list   Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    My bibliography  
  11. Undecidability in Rn: Riddled Basins, the KAM Tori, and the Stability of the Solar System.Matthew W. Parker - 2003 - Philosophy of Science 70 (2):359-382.
    Some have suggested that certain classical physical systems have undecidable long-term behavior, without specifying an appropriate notion of decidability over the reals. We introduce such a notion, decidability in (or d- ) for any measure , which is particularly appropriate for physics and in some ways more intuitive than Ko's (1991) recursive approximability (r.a.). For Lebesgue measure , d- implies r.a. Sets with positive -measure that are sufficiently "riddled" with holes are never d- but are often r.a. This explicates Sommerer (...)
    Remove from this list   Direct download (8 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  12. Fourteen Arguments in Favour of a Formalist Philosophy of Real Mathematics.Karlis Podnieks - 2015 - Baltic Journal of Modern Computing 3 (1):1-15.
    The formalist philosophy of mathematics (in its purest, most extreme version) is widely regarded as a “discredited position”. This pure and extreme version of formalism is called by some authors “game formalism”, because it is alleged to represent mathematics as a meaningless game with strings of symbols. Nevertheless, I would like to draw attention to some arguments in favour of game formalism as an appropriate philosophy of real mathematics. For the most part, these arguments have not yet been used or (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  13. Wolpert, Chaitin and Wittgenstein on Impossibility, Incompleteness, the Limits of Computation, Theism and the Universe as Computer-the Ultimate Turing Theorem.Michael Starks - 2017 - Philosophy, Human Nature and the Collapse of Civilization Michael Starks 3rd Ed. (2017).
    I have read many recent discussions of the limits of computation and the universe as computer, hoping to find some comments on the amazing work of polymath physicist and decision theorist David Wolpert but have not found a single citation and so I present this very brief summary. Wolpert proved some stunning impossibility or incompleteness theorems (1992 to 2008-see arxiv.org) on the limits to inference (computation) that are so general they are independent of the device doing the computation, and even (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography