Also, if you’re going to measure information content, you really need to fix a formal language first, or else “the number of bits needed to express X” is ill-defined.
Basically, learn model theory before trying to wield it.
I don’t know model theory, but isn’t the crucial detail here whether or not the number of bits needed to express X is finite or infinite? If so, then it seems we can handwave the specific formal language we’re using to describe X, in the same way that we can handwave what encoding for Turing Machines generally when talking about Kolmogorov complexity, even though to actually get a concrete integer K(S) representing the Kolmogorovo complexity of a string S requires us to use a fixed encoding of Turing Machines. In practice, we never actually care what the number K(S) is.
Let’s say I have a specific model of the real numbers in mind, and lets pretend “number of bits needed to describe X” means “log2 the length of the shortest theory that proves the existence of X.”
Fix a language L1 whose constants are the rational numbers and which otherwise is the language of linear orders. Then it takes a countable number of propositions to prove the existence of any given irrational number (i.e., exists x[1] such that x[1] < u[1], …, exists y[1] such that y[1] > v[1], …, x[1] = y[1], … x[1] = x[2], …, where the sequences u[n] and v[n] are strict upper and lower bounding sequences on the real number in question).
Now fix a language L2 whose constants are the real numbers. It now requires one proposition to prove the existence of any given irrational number (i.e., exists x such that x = c).
The difference between this ill-defined measure of information and Kolomogrov complexity is that Turing Machines are inherently countable, and the languages and models of model theory need not be.
(Disclaimer: paper-machine2011 knew far more about mathematical logic than paper-machine2016 does.)
The definition “length of the shortest program which minimizes (program length + runtime)” isn’t undecideable, although you could argue that that’s not what we normally mean by number of bits.
I don’t know model theory, but isn’t the crucial detail here whether or not the number of bits needed to express X is finite or infinite? If so, then it seems we can handwave the specific formal language we’re using to describe X, in the same way that we can handwave what encoding for Turing Machines generally when talking about Kolmogorov complexity, even though to actually get a concrete integer K(S) representing the Kolmogorovo complexity of a string S requires us to use a fixed encoding of Turing Machines. In practice, we never actually care what the number K(S) is.
Let’s say I have a specific model of the real numbers in mind, and lets pretend “number of bits needed to describe X” means “log2 the length of the shortest theory that proves the existence of X.”
Fix a language L1 whose constants are the rational numbers and which otherwise is the language of linear orders. Then it takes a countable number of propositions to prove the existence of any given irrational number (i.e., exists x[1] such that x[1] < u[1], …, exists y[1] such that y[1] > v[1], …, x[1] = y[1], … x[1] = x[2], …, where the sequences u[n] and v[n] are strict upper and lower bounding sequences on the real number in question).
Now fix a language L2 whose constants are the real numbers. It now requires one proposition to prove the existence of any given irrational number (i.e., exists x such that x = c).
The difference between this ill-defined measure of information and Kolomogrov complexity is that Turing Machines are inherently countable, and the languages and models of model theory need not be.
(Disclaimer: paper-machine2011 knew far more about mathematical logic than paper-machine2016 does.)
Whether a theory proves the existence of X may be an undecideable question.
How many bits it takes to describe X is an undecidable question when defined in other ways, too.
The definition “length of the shortest program which minimizes (program length + runtime)” isn’t undecideable, although you could argue that that’s not what we normally mean by number of bits.
Adding program length and runtime feels to me like a type error.