[mmarx]

Decidability (as a property of decision problems like the halting problem) is a different notion, though: In the context of incompleteness, an undecidable statement is a statement that cannot be proven or disproved in that system. Decidability of a decision problem is concerned with an effective procedure that, for every instance of the problem, answers yes/no. Specifically for a logical theory, decidability of this theory is deciding for any formula in the same language whether it follows from the theory as a logical consequence.

Neither incompleteness nor undecidability imply the other[0].

[0] https://en.wikipedia.org/wiki/Decidability_(logic)#Relations...

[pron]

Incompleteness does not imply undecidability, but undecidability implies incompleteness, because completeness implies decidability: in a complete system (powerful enough to describe Turing machines), for every TM M and input x, there's a theorem saying that M halts or one that M doesn't halt (because the system is complete). To decide halting, we therefore just need to enumerate all theorems in the system, and we are guaranteed to stop and find the deciding theorem[1].

In fact, when Gödel saw Turing's work and was convinced that Turing indeed captured the general notion of a formal system, he said that the incompleteness theorem was finally satisfactorily proven for all formal systems.

[1]: See http://www.scottaaronson.com/blog/?p=710