Acceptable Complexity Measures of Theorems

Details Acceptable Complexity Measures of Theorems Acceptable Complexity Measures of Theorems

2009-09-30

arxiv.org/abs/0910.0045v1

Complex Systems 18:4 (2010) 403-425

Computer Science

Logic in Computer Science

16 pages, presented at NKS Midwest Conference '08

Scientific paper

In 1931, G\"odel presented in K\"onigsberg his famous Incompleteness Theorem, stating that some true mathematical statements are unprovable. Yet, this result gives us no idea about those independent (that is, true and unprovable) statements, about their frequency, the reason they are unprovable, and so on. Calude and J\"urgensen proved in 2005 Chaitin's "heuristic principle" for an appropriate measure: the theorems of a finitely-specified theory cannot be significantly more complex than the theory itself. In this work, we investigate the existence of other measures, different from the original one, which satisfy this "heuristic principle". At this end, we introduce the definition of acceptable complexity measure of theorems.

Affiliated with

Also associated with

No associations

Rating

Acceptable Complexity Measures of Theorems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Acceptable Complexity Measures of Theorems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acceptable Complexity Measures of Theorems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-141670