Re: Godel's incompleteness theorem vs Church's/Turings work

Incompleteness (i.e., Godel's Theorem) : there are sentences S in the
language of arithmetic such that neither S nor ~S are provable from Q.

Undecidability (i.e., Church and Turing's Theorem): there is no
mechanical way to determine the validity of an argument in first order
logic -- that is to say, the set of theorems of first order logic is
uncomputable.

Both of these statements follow from the unsolvability of the halting
problem, and the Sigma_1 representability of all r.e sets in a similar
way, but they nevertheless say quite distinct things.

Kevin.


falcon wrote:
I understand that Godel showed that any (axiomatic?) system is
incomplete (in 1931 according to a reference I can no longer find).
Around 1936, Church showed that first order logic and peano arithmetic
are undecidable...in the same year Turing showed the halting problem
(mostly according to wikipedia).

So what is the difference between Godel's theorem and later work of
Church and Turing?

.

Relevant Pages