Forbidden Information

There appears to be a gap between usual interpretations of Godel Theorem and what is actually proven. Closing this gap does not seem obvious and involves complexity theory. (This is unrelated to, well studied before, complexity quantifications of the usual Godel effects.) Similar problems and answers apply to other unsolvability results for tasks where required solutions are not unique, such as, e. g. , non-recursive tilings.

Authors

• Leonid A. Levin

Keywords

• Computer science
• Formal System
• Mutual Information
• Linear Complexity
• Infinite Sequence
• Program Length