A problem is called partially decidable, semi-decidable, solvable, or provable if A is a recursively enumerable set.
This weaker form differs from the standard statement of the incompleteness theorem by asserting that an axiomatization of the natural numbers that is both complete and sound is impossible.
The "sound" part is the weakening: it means that we require the axiomatic system in question to prove only true statements about natural numbers.
[3] Assume that we have a sound (and hence consistent) and complete axiomatization of all true first-order logic statements about natural numbers.
Since we know that there cannot be such an algorithm, it follows that the assumption that there is a consistent and complete axiomatization of all true first-order logic statements about natural numbers must be false.
The second sense is used in relation to computability theory and applies not to statements but to decision problems, which are countably infinite sets of questions each requiring a yes or no answer.
Whether there exist so-called "absolutely undecidable" statements, whose truth value can never be known or is ill-specified, is a controversial point among various philosophical schools.
Matiyasevich showed this problem to be unsolvable by mapping a Diophantine equation to a recursively enumerable set and invoking Gödel's Incompleteness Theorem.
Kruskal's tree theorem, which has applications in computer science, is also undecidable from the Peano axioms but provable in set theory.
In fact Kruskal's tree theorem (or its finite form) is undecidable in a much stronger system codifying the principles acceptable on basis of a philosophy of mathematics called predicativism.
Goodstein's theorem is a statement about the Ramsey theory of the natural numbers that Kirby and Paris showed is undecidable in Peano arithmetic.
Gregory Chaitin produced undecidable statements in algorithmic information theory and proved another incompleteness theorem in that setting.
Chaitin's theorem states that for any theory that can represent enough arithmetic, there is an upper bound c such that no specific number can be proven in that theory to have Kolmogorov complexity greater than c. While Gödel's theorem is related to the liar paradox, Chaitin's result is related to Berry's paradox.