Skip to main content
MathOverflow

Return to Question

Became Hot Network Question
added 291 characters in body
Source Link
truebaran
truebaran
  • 9.3k
  • 5
  • 30
  • 88

Chaitin's incompleteness theorem roughly saying states that for any theory $S$ there exists universal constant $L$ that for any string $\sigma$ one cannot prove (within this theory) that $K(\sigma)>L$ where $K$ is the Kolmogorov complexity. Since this constant is universal I'm very curious

How one can estimate thisconstant for some well known theories (Peano arithmetic is the first one which comes to my mind but the answer would be even more interesting for ZFC)-for example could it be compared with Busy Beaver numbers?

I suspect that in order to say anything about such a constant one has to use some richer theory so for ZFC I would be also interested what axioms do we have to add to $ZFC$?

EDIT: adressing a comment below: I'm not sure whether it is enough but I would like to stick to Turing model of computation: namely fix some universal Turning machine and then ask my questions: please, correct me if it is still not enough information for my question to be well posed

Chaitin's incompleteness theorem roughly saying states that for any theory $S$ there exists universal constant $L$ that for any string $\sigma$ one cannot prove (within this theory) that $K(\sigma)>L$ where $K$ is the Kolmogorov complexity. Since this constant is universal I'm very curious

How one can estimate thisconstant for some well known theories (Peano arithmetic is the first one which comes to my mind but the answer would be even more interesting for ZFC)-for example could it be compared with Busy Beaver numbers?

I suspect that in order to say anything about such a constant one has to use some richer theory so for ZFC I would be also interested what axioms do we have to add to $ZFC$?

Chaitin's incompleteness theorem roughly saying states that for any theory $S$ there exists universal constant $L$ that for any string $\sigma$ one cannot prove (within this theory) that $K(\sigma)>L$ where $K$ is the Kolmogorov complexity. Since this constant is universal I'm very curious

How one can estimate thisconstant for some well known theories (Peano arithmetic is the first one which comes to my mind but the answer would be even more interesting for ZFC)-for example could it be compared with Busy Beaver numbers?

I suspect that in order to say anything about such a constant one has to use some richer theory so for ZFC I would be also interested what axioms do we have to add to $ZFC$?

EDIT: adressing a comment below: I'm not sure whether it is enough but I would like to stick to Turing model of computation: namely fix some universal Turning machine and then ask my questions: please, correct me if it is still not enough information for my question to be well posed

Source Link
truebaran
truebaran
  • 9.3k
  • 5
  • 30
  • 88

(Very) Large numbers, Chaitin's incompletness theorem and a specific upper bound

Chaitin's incompleteness theorem roughly saying states that for any theory $S$ there exists universal constant $L$ that for any string $\sigma$ one cannot prove (within this theory) that $K(\sigma)>L$ where $K$ is the Kolmogorov complexity. Since this constant is universal I'm very curious

How one can estimate thisconstant for some well known theories (Peano arithmetic is the first one which comes to my mind but the answer would be even more interesting for ZFC)-for example could it be compared with Busy Beaver numbers?

I suspect that in order to say anything about such a constant one has to use some richer theory so for ZFC I would be also interested what axioms do we have to add to $ZFC$?