With regards to thought experiment 2, I think a useful reference point is completely random strings of digits. If you were indeed picking the strings of digits totally at random, you would expect a distribution in which: 1) Any string of digits is equally likely. 2) A significant majority of the strings has complexity of roughly m (plus some constant overhead).
Now, in the actual thought experiment, the string of digits is quite obviously not random; as you’ve said, the Kolmogorov complexity has a hard upper bound of C + log(m) + log(n), which in general could be significantly smaller than m.
Here’s one alternative hypothesis that I can think of, which makes sense to me but could easily be wrong: H2: In general, such strings will appear to be mostly random, except for the simple fact that they actually occur relatively early in pi. If this is true, one would expect that for quite a lot of those strings there will not be a more compact representation than a program that, in one way or another, explicitly computes those digits of pi.
Also, I think I’ve thought of an interesting way of testing a prediction along the lines you’ve suggested. If we take S(n, m, pi) to mean “the m digits following the nth digit of pi”, let’s define N(s, pi) := the smallest integer n such that S(n, len(s), pi) = s
If, as you suggest, simpler strings should be “more likely”, then it would follow that for simpler strings s, you would expect to see lower values of N(s, pi). In particular, how about the following experiments: i) Generate a bunch of random sequences R (all of length m) and look at the distribution you get for N(r, pi). You can also use your apparent complexity checker on those sequences, but in general you would expect most of them to have complexity of roughly m. ii) Pick out a bunch of strings Q that are demonstrably simple, e.g. 0000000000, 1111111111, 0123456789, and look at the values you get for N(q, pi) iii) Pick a different number, which you think has similar properties to pi in this regard—let’s say e. Now, for a given number n, you can calculate F(n) := N(S(n, m, e), pi) which basically means “for a sequence occurring at position n in e, what position does it first occur at in pi”?
I think if your hypothesis is true, it will hold that the values for (ii) are typically much smaller than the values in (i), and the values for F(n) in (iii) will generally tend to increase as n increases (up to a finite limit, because eventually you will have covered all sequences of length m). On the other hand, if H2 is correct, the values for (i), (ii), and (iii) will all be pretty similar.
Now, with all that being said, I’m not sure that your thought experiment #2 carries across to a prior as to whether or not certain logical statements are true. It may be an interesting experiment to actually try in practice, though.
A useful point of contrast is the idea of a normal number, as pi and e are widely believed to be. The crucial difference is that normal-ness requires the asymptotic frequencies to be the same for all strings of the same length, which is very different to the criterion I mentioned above.
With regards to thought experiment 2, I think a useful reference point is completely random strings of digits. If you were indeed picking the strings of digits totally at random, you would expect a distribution in which:
1) Any string of digits is equally likely.
2) A significant majority of the strings has complexity of roughly m (plus some constant overhead).
Now, in the actual thought experiment, the string of digits is quite obviously not random; as you’ve said, the Kolmogorov complexity has a hard upper bound of C + log(m) + log(n), which in general could be significantly smaller than m.
Here’s one alternative hypothesis that I can think of, which makes sense to me but could easily be wrong:
H2: In general, such strings will appear to be mostly random, except for the simple fact that they actually occur relatively early in pi.
If this is true, one would expect that for quite a lot of those strings there will not be a more compact representation than a program that, in one way or another, explicitly computes those digits of pi.
Also, I think I’ve thought of an interesting way of testing a prediction along the lines you’ve suggested. If we take S(n, m, pi) to mean “the m digits following the nth digit of pi”, let’s define
N(s, pi) := the smallest integer n such that S(n, len(s), pi) = s
If, as you suggest, simpler strings should be “more likely”, then it would follow that for simpler strings s, you would expect to see lower values of N(s, pi). In particular, how about the following experiments:
i) Generate a bunch of random sequences R (all of length m) and look at the distribution you get for N(r, pi). You can also use your apparent complexity checker on those sequences, but in general you would expect most of them to have complexity of roughly m.
ii) Pick out a bunch of strings Q that are demonstrably simple, e.g. 0000000000, 1111111111, 0123456789, and look at the values you get for N(q, pi)
iii) Pick a different number, which you think has similar properties to pi in this regard—let’s say e. Now, for a given number n, you can calculate
F(n) := N(S(n, m, e), pi)
which basically means “for a sequence occurring at position n in e, what position does it first occur at in pi”?
I think if your hypothesis is true, it will hold that the values for (ii) are typically much smaller than the values in (i), and the values for F(n) in (iii) will generally tend to increase as n increases (up to a finite limit, because eventually you will have covered all sequences of length m). On the other hand, if H2 is correct, the values for (i), (ii), and (iii) will all be pretty similar.
Now, with all that being said, I’m not sure that your thought experiment #2 carries across to a prior as to whether or not certain logical statements are true. It may be an interesting experiment to actually try in practice, though.
A useful point of contrast is the idea of a normal number, as pi and e are widely believed to be. The crucial difference is that normal-ness requires the asymptotic frequencies to be the same for all strings of the same length, which is very different to the criterion I mentioned above.