3 ms·
The parent suggested that the number couldn't be encoded due to its largeness rather than its value. So while any number n with Kolmogorov complexity K(n) > 10^
by tromp 1y ago
The parent suggested that the number couldn't be encoded due to its largeness rather than its value. So while any number n with Kolmogorov complexity K(n) > 10^100 cannot be recursively encoded in the known universe, that number n need only be 10^100 bits long. On the other hand a number that's too large to be recursively encoded in the known universe would have to exceed BBλ2(10^100),
where BBλ2 is an optimal busy beaver for prefix-free binary programs [1].
[1] https://oeis.org/A361211 https://oeis.org/A361211
- BlackFly 1y agoYes, I understood what the parent suggested. I am pointing out that such a number may have strange properties like the fact that a number larger than it can have a smaller Kolmogorov complexity, then I am questioning whether there is a number such that every number larger than it has such a large Kolmogorov complexity that it cannot be encoded. The question therefore becomes, is there a limit to the size of physically describable numbers? Or is there always going to be some number larger with some trivial kolmogorov complexity?
- ccvannorman 1y agoI absolutely love this question. Postulate: You cannot define a largest physically describable number. My assumption is that due to the very nature of Kolmogorov complexity (and other Godel related / halting problem related / self referential descriptions), this is not an answerable or sensible question. It falls under the same language-enabled recursion problems as: - The least number that cannot be described in less than twenty syllables. - The least number that cannot be uniquely described by an expression of first-order set theory that contains no more than a googol (10^100) symbols.
- tromp 1y agoBeyond BBλ2(10^100), there is no larger number with complexity under 10^100.