MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 edited title

1

# Gödel's Theorem and the complexity of arithmetic

In How complicated can structures be? Jouko Väänänen says:

The guiding result of mathematical logic is the Incompleteness Theorem of Gödel, which says that the logical structure of number theory is so complicated that it cannot be effectively axiomatized in its entirety. In other words, the theory is non-recursive, i.e. there is no Turing machine that could tell whether a sentence of number theory is true or not.

I've never seen Gödel's Incompleteness Theorem this way: that it's a matter of the overall complexity of the structure of the natural numbers that there are facts about them that cannot be proved.

So I wonder whether I can take the quote above literally:

Can Gödel's Theorem be rigorously stated in terms of complexity?

Somehow like this: "Every system which exceeds complexity threshold X is undecidable."

Or is it just a vague paraphrase, not to be taken too seriously?