The discussion centers on the Kolmogorov complexity of irrational numbers, specifically addressing whether noncomputable reals possess infinite complexity. Participants confirm that noncomputable numbers indeed have infinite complexity. An example illustrates that interspersing zeros in a noncomputable number can reduce the information required to compute segments of that number, indicating that not all noncomputable numbers exhibit the same level of randomness. This highlights the nuanced nature of complexity in noncomputable numbers.
PREREQUISITESMathematicians, computer scientists, and students interested in theoretical computer science, particularly those exploring the concepts of Kolmogorov complexity and noncomputable numbers.
cragar said:How would I figure out the Kolmogorov complexity of an irrational number?
Could I just look at the shortest formula to compute that number.
If it is an uncomputable real, does it have infinite complexity?
SteveL27 said:I saw an interesting example online the other day. Take a noncomputable number and interperse 0's in every other digit position. Then for each finite-length initial segment, it takes just a little more than half as much information to compute the number with the 0's in every other position as it does to compute the original number. So not all noncomputable numbers are equally random. It's tricker than I'd realized.