Edited by Jordan Bohall (University of Illinois, Urbana-Champaign)
|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)|
Using PhilPapers from home?
Create an account to enable off-campus access through your institution's proxy server.
Monitor this page
Be alerted of all new items appearing on this page. Choose how you want to monitor it:
David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jonathan Jenkins Ichikawa
Jack Alan Reynolds
Learn more about PhilPapers