Editing Gödel's incompleteness theorems (section)

== Relationship with computability ==
{{See also|Halting problem#Gödel's incompleteness theorems}}
The incompleteness theorem is closely related to several results about [[undecidable set]]s in [[recursion theory]].

{{harvtxt|Kleene|1943}} presented a proof of Gödel's incompleteness theorem using basic results of computability theory. One such result shows that the [[halting problem]] is undecidable: no computer program can correctly determine, given any program {{mvar|P}} as input, whether {{mvar|P}} eventually halts when run with a particular given input. Kleene showed that the existence of a complete effective system of arithmetic with certain consistency properties would force the halting problem to be decidable, a contradiction.{{sfn|Kleene|1943}} This method of proof has also been presented by {{harvtxt|Shoenfield|1967}}; {{harvtxt|Charlesworth|1981}}; and {{harvtxt|Hopcroft|Ullman|1979}}.{{sfnm
 | 1a1 = Shoenfield | 1y = 1967 | 1p = 132
 | 2a1 = Charlesworth | 2y = 1981
 | 3a1 = Hopcroft | 3a2 = Ullman | 3y = 1979
}}

{{harvtxt|Franzén|2005}} explains how [[Matiyasevich's theorem|Matiyasevich's solution]] to [[Hilbert's 10th problem]] can be used to obtain a proof to Gödel's first incompleteness theorem.{{sfn|Franzén|2005|p=73}} [[Yuri Matiyasevich|Matiyasevich]] proved that there is no algorithm that, given a multivariate polynomial {{math|''p''(''x''<sub>1</sub>, ''x''<sub>2</sub>,...,''x''<sub>k</sub>)}} with integer coefficients, determines whether there is an integer solution to the equation {{mvar|p}} = 0. Because polynomials with integer coefficients, and integers themselves, are directly expressible in the language of arithmetic, if a multivariate integer polynomial equation {{mvar|p}} = 0 does have a solution in the integers then any sufficiently strong system of arithmetic {{mvar|T}} will prove this. Moreover, suppose the system {{mvar|T}} is ω-consistent. In that case, it will never prove that a particular polynomial equation has a solution when there is no solution in the integers. Thus, if {{mvar|T}} were complete and ω-consistent, it would be possible to determine algorithmically whether a polynomial equation has a solution by merely enumerating proofs of {{mvar|T}} until either "{{mvar|p}} has a solution" or "{{mvar|p}} has no solution" is found, in contradiction to Matiyasevich's theorem. Hence it follows that {{mvar|T}} cannot be ω-consistent and complete. Moreover, for each consistent effectively generated system {{mvar|T}}, it is possible to effectively generate a multivariate polynomial {{mvar|p}} over the integers such that the equation {{mvar|p}} = 0 has no solutions over the integers, but the lack of solutions cannot be proved in {{mvar|T}}.{{sfnm
 | 1a1 = Davis | 1y = 2006 | 1p = 416
 | 2a1 = Jones | 2y = 1980
}}

{{harvtxt|Smoryński|1977}} shows how the existence of [[recursively inseparable sets]] can be used to prove the first incompleteness theorem. This proof is often extended to show that systems such as Peano arithmetic are [[essentially undecidable]].{{sfnm
 | 1a1 = Smoryński | 1y = 1977 | 1p = 842
 | 2a1 = Kleene | 2y = 1967 | 2p = 274
}}

[[Chaitin's incompleteness theorem]] gives a different method of producing independent sentences, based on [[Kolmogorov complexity]]. Like the proof presented by Kleene that was mentioned above, Chaitin's theorem only applies to theories with the additional property that all their axioms are true in the standard model of the natural numbers. Gödel's incompleteness theorem is distinguished by its applicability to consistent theories that nonetheless include false statements in the standard model; these theories are known as [[ω-consistent theory|ω-inconsistent]].