If I were to roll a die infinitely many times, assuming the result was truly random, and use the results as the decimal places of a number, would that number (likely) be an uncomputable number?
Asked
Active
Viewed 167 times
6
-
2If you have a countable number of computable numbers then ... – Henry Oct 24 '22 at 14:31
-
By Borel-Cantelli it should be transcendental – maxjw91 Oct 24 '22 at 15:13
-
1@maxjw91 Yes, but some transcendenttal numbers are computable. Also, Borel-Cantelli is overkill here. – Andreas Blass Oct 24 '22 at 16:30
-
If you determine the digits actually randomly , the probability is $1$ that you will get an uncomputable number. – Peter Oct 24 '22 at 16:40
1 Answers
6
Yes. There are only countably many computable numbers (because there are only countably many computer programs), so a random real number, say in the interval $[0, 1]$ to be concrete, is uncomputable with probability $1$.
In fact with probability $1$ it will have a much stronger property called algorithmic randomness, which roughly speaking says that the digits are incompressible.
Qiaochu Yuan
- 419,620
-
The real lesson here is that "assuming that the digits are truly random" is an extremely strong assumption. In practice it's unclear how you could ever come to believe this... – Qiaochu Yuan Oct 24 '22 at 17:39
-
Hilariously (to my mind) probably the most practical way to ascertain "randomness" is, as you say, to appraise compressibility... but actual Kolmogorov-etal complexity is not computable, either... so just run a few of the standard compression algorithms and see what happens? :) – paul garrett Oct 24 '22 at 18:03