Acceptable Complexity Measures of Theorems
Bruno Grenet
Laboratoire de l’Informatique du Parallélisme
École Normale supérieure de Lyon
46, allée d’Italie
69 364 Lyon Cedex 07, France
bruno.grenet@ens-lyon.fr
Abstract
In 1931 Gödel [1] presented his famous incompleteness theorem in Königsberg, stating that some true mathematical statements are unprovable. Yet, this result gives us no idea about those independent (i.e., true and unprovable) statements, about their frequency, the reason they are unprovable, and so on. In 2005 Calude and Jürgensen [2] proved Chaitin’s “heuristic principle” for an appropriate measure: the theorems of a finitely specified theory cannot be significantly more complex than the theory itself [3]. In this paper, we investigate the existence of other measures, different from the original, that satisfy this heuristic principle. Toward this end, we introduce a definition for acceptable complexity measures of theorems.
