Re: Godel's incompleteness theorem vs Church's/Turings work
- From: Frederick Williams <Frederick.Williams1@xxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Sun, 09 Apr 2006 10:05:33 GMT
falcon wrote:
I understand that Godel showed that any (axiomatic?) system is
incomplete
He showed that a consistent system containing a modest amount of
arithmetic is incomplete.
(in 1931 according to a reference I can no longer find).
\"Uber formal unentscheidbare S\"atze der Principia mathematica und
verwandter Systeme I, Monatsshefte f\"ur Mathematik und Physik 38,
173-198. English translations in: Jean van Heijenoort, From Frege to
G\"odel, Harvard UP; G\"odel, On formally undecidable propositions of
Principia mathematica and related systems, trans. B Metzler, Oliver and
Boyd; Martin Davis (ed), The undecidable. Basic papers on undecidable
propositions, unsolvable problems, and computable functions, Raven
Press; Solomon Feferman, et al, eds, Kurt G\"odel Collected Works, vol
I, Oxford U P.
Around 1936, Church showed that first order logic and peano arithmetic
are undecidable...in the same year Turing showed the halting problem
See the Davis collection for both these papers.
(mostly according to wikipedia).
So what is the difference between Godel's theorem and later work of
Church and Turing?
Incompleteness and undecidable are different things. This is
illustrated by FOL: it is complete (G\"odel again) but undecidable. To
say that something can't be done you need to define what it means to
"do". Turing made this clear by reference to an idealized computer.
--
Remove "antispam" and ".invalid" for e-mail address.
.
- Follow-Ups:
- References:
- Prev by Date: Re: "Countably Well-Ordered" ?
- Next by Date: A Simple "Proof" of Fermat's Last Theorem
- Previous by thread: Godel's incompleteness theorem vs Church's/Turings work
- Next by thread: Re: Godel's incompleteness theorem vs Church's/Turings work
- Index(es):
Relevant Pages
|
