5 ms·

But none of those are really random either. The only sensible definition of randomness here is Kolmogorov complexity, and all of those numbers you just mentione

by OskarS 8y ago

But none of those are really random either. The only sensible definition of randomness here is Kolmogorov complexity, and all of those numbers you just mentioned have incredibly low Kolmogorov complexity. I can write a tiny computer program that prints them out to billions of digits. What the author is probably referring to is "non-computable numbers", which are numbers that cannot be computed to arbitrary precision by ANY Turing machine. But it's incredibly confusing and wrong to use the term "real numbers" to mean "non-computable numbers".

sykh 8y ago
A normal number can be computable. It is not known if sqrt(2) is normal.
- OskarS 8y ago
  At no point was anybody talking about normal numbers. "Normal numbers" doesn't mean "numbers with random digits", it has a much narrower meaning that. There are non-computable numbers which are normal, there are non-computable numbers which aren't. There are computable numbers that are normal that don't look random in the least: https://en.wikipedia.org/wiki/Champernowne_constant https://en.wikipedia.org/wiki/Champernowne_constant
  - sykh 8y ago
    The author's paper is about normal numbers (numbers that contain infinite amount of information). If a normal number isn't considered to have random digits then what notion would you use?
    - OskarS 8y ago
      You've misunderstood the definition of normal numbers. A "normal number" (loosely defined) is a number where the digit expansion of the number has all possible substrings of digits uniformly distributed in the limit as it goes to infinity. Several things to note: 1. Whether or not a number is normal has nothing to do with the "randomness" of its digits or the "amount of information" in the digits. Chapernowne's constant, 0.123456789101112... isn't "random" at all and contains very little information, yet it is known to be normal in base 10. 2. A number can have totally super-random digits (as random as you want! it can even be non-computable! infinite information!) and not be normal at all. For instance, imagine you have a normal number that's as random as you want, and it starts like: 0.892345123402345671235.... And then goes on forever, no discernible pattern. Say you construct a new number from this number, with the only difference being that you remove the digit 7. Literally, every place that a 7 appears in your original number, you just remove it. This number would no longer be a normal number, because all the sequences with the number 7 in it would appear nowhere. The number would still have "infinite information" in the sense of the author of this paper. It would still be "just as random", it would still have "no pattern". But it would not be a normal number anymore. Whether or not a number is "normal" or not has nothing to do with the issues raised in this paper. "Normality" is a different criterion entirely. When the author talks about numbers with "infinite information", he's not talking about normal numbers, he's talking about computable numbers, which is an entirely different concept: https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number
      - sykh 8y ago
        I read through most of the paper we are all nominally talking about. He doesn't use normal numbers as you say. He is talking about computable numbers as you say. My apologies. But a normal number has "random" digits in the sense that all finite sequences of digits (in a given base) occurs uniformly in the expansion. What other notion of random can one meaningfully give for an expansion of a number's digits? Without getting into too much philosophy. From [1]: We call a real number b-normal if, qualitatively speaking, its base-b digits are “truly random. My expertise is in commutative algebra so I'm outside of my comfort zone. [1]: https://www.davidhbailey.com/dhbpapers/bcnormal.pdf https://www.davidhbailey.com/dhbpapers/bcnormal.pdf
        OskarS 8y ago
        Something can be random and not have a uniform distribution. If I throw two dice, the sum will be random, but it will not be uniformly distributed. Uniform is just one distribution among meny. The only definition of "randomness" in a sequence that holds any kind of water, philosophically or mathematically, is Kolmogorov complexity [0] (see specifically the section on "Kolmogorov randomness"). I don't know where you got the idea that "normalness" is the ultimate version of randomness, but it's not. Forget the formal definition for a second, and just think of the intuitive notion of randomness for a second: does the sequence 12345678.... look random to you? In random sequences there should be no patterns: do you see a pattern in this sequence? If you had a computer program with a random number generator that produced that sequence of digits, would you be happy with it? No, you wouldn't. In the sense of Kolmogorov randomness, the sequence 1234567.... is obviously not random at all, since it's trivial to find a Turing machine to generate it. It matches up perfectly with out intuitive notion of what randomness is, and it quite correctly points out that the amount of information in the string is very low, even though it's infinitely long. That is my definition of randomness, and it's (more or less) the author of this paper's definition. [0]: https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
      - throwawaymath 8y ago
        > Chapernowne's constant, 0.123456789101112... isn't "random" at all and contains very little information, yet it is known to be normal in base 10. Why is Chapernowne's constant not random? > The number would still have "infinite information" in the sense of the author of this paper. It would still be "just as random", it would still have "no pattern". But it would not be a normal number anymore. That's not true. It would not be just as random. If the set you're sampling from includes a 7 (i.e. the set of digits which can be represented in any single place in the sequence), and you never see a 7 for an extremely long time, this is exceptionally good heuristic evidence that the number is not random. And if we know 7 never shows up, we also know that the number is not random, because we know it's not uniformly sampling from the set of base 10 digits.
candiodari 8y ago
Okay, but 2 points: 1) Kolmogorov complexity is a measure of the computational resources needed to specify the object Depending on what you mean by "specify the object" this may or may not be infinite resources. My vote goes to infinite. Because you either need infinite resources even to just express this number, or you need infinite resources to actually run it. I get that you can create a finite program that gives an approximation of the number, but that's not the same, and only approximations can be finite. The number itself, and it's useful specifications, are all infinite. For the real number you need infinite resources to express it. So by what measure exactly does sqrt(2) have finite complexity ? In fact, you could use the old "every number occurs in Pi" trick and say that every other object is contained within it (and within every other real number), and since kolmogorov complexity is a metric I have just proven that the kolmogorov complexity of sqrt(2) is larger than any other kolmogorov complexity. The only number that satisfies that condition is infinite. 2) Even if this applies to the 4 numbers I specified, or the few thousand "well known" real numbers, it doesn't apply to any real proportion of real numbers. I mean, I can compute one or two 3rd degree boundary differential equations straight in my head, but that is very different from saying I can do that in the general case. Hell, quantum computers can't do it in the general case. The same is true for specifying real numbers. (and, more or less) 3) in reality, only approximations of sqrt(2) are computable. The real number itself isn't.

by OskarS 8y ago

sykh 8y ago

A normal number can be computable. It is not known if sqrt(2) is normal.

OskarS 8y ago
At no point was anybody talking about normal numbers. "Normal numbers" doesn't mean "numbers with random digits", it has a much narrower meaning that. There are non-computable numbers which are normal, there are non-computable numbers which aren't. There are computable numbers that are normal that don't look random in the least: https://en.wikipedia.org/wiki/Champernowne_constant https://en.wikipedia.org/wiki/Champernowne_constant
- sykh 8y ago
  The author's paper is about normal numbers (numbers that contain infinite amount of information). If a normal number isn't considered to have random digits then what notion would you use?
  - OskarS 8y ago
    You've misunderstood the definition of normal numbers. A "normal number" (loosely defined) is a number where the digit expansion of the number has all possible substrings of digits uniformly distributed in the limit as it goes to infinity. Several things to note: 1. Whether or not a number is normal has nothing to do with the "randomness" of its digits or the "amount of information" in the digits. Chapernowne's constant, 0.123456789101112... isn't "random" at all and contains very little information, yet it is known to be normal in base 10. 2. A number can have totally super-random digits (as random as you want! it can even be non-computable! infinite information!) and not be normal at all. For instance, imagine you have a normal number that's as random as you want, and it starts like: 0.892345123402345671235.... And then goes on forever, no discernible pattern. Say you construct a new number from this number, with the only difference being that you remove the digit 7. Literally, every place that a 7 appears in your original number, you just remove it. This number would no longer be a normal number, because all the sequences with the number 7 in it would appear nowhere. The number would still have "infinite information" in the sense of the author of this paper. It would still be "just as random", it would still have "no pattern". But it would not be a normal number anymore. Whether or not a number is "normal" or not has nothing to do with the issues raised in this paper. "Normality" is a different criterion entirely. When the author talks about numbers with "infinite information", he's not talking about normal numbers, he's talking about computable numbers, which is an entirely different concept: https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number
    - sykh 8y ago
      I read through most of the paper we are all nominally talking about. He doesn't use normal numbers as you say. He is talking about computable numbers as you say. My apologies. But a normal number has "random" digits in the sense that all finite sequences of digits (in a given base) occurs uniformly in the expansion. What other notion of random can one meaningfully give for an expansion of a number's digits? Without getting into too much philosophy. From [1]: We call a real number b-normal if, qualitatively speaking, its base-b digits are “truly random. My expertise is in commutative algebra so I'm outside of my comfort zone. [1]: https://www.davidhbailey.com/dhbpapers/bcnormal.pdf https://www.davidhbailey.com/dhbpapers/bcnormal.pdf
      - OskarS 8y ago
        Something can be random and not have a uniform distribution. If I throw two dice, the sum will be random, but it will not be uniformly distributed. Uniform is just one distribution among meny. The only definition of "randomness" in a sequence that holds any kind of water, philosophically or mathematically, is Kolmogorov complexity [0] (see specifically the section on "Kolmogorov randomness"). I don't know where you got the idea that "normalness" is the ultimate version of randomness, but it's not. Forget the formal definition for a second, and just think of the intuitive notion of randomness for a second: does the sequence 12345678.... look random to you? In random sequences there should be no patterns: do you see a pattern in this sequence? If you had a computer program with a random number generator that produced that sequence of digits, would you be happy with it? No, you wouldn't. In the sense of Kolmogorov randomness, the sequence 1234567.... is obviously not random at all, since it's trivial to find a Turing machine to generate it. It matches up perfectly with out intuitive notion of what randomness is, and it quite correctly points out that the amount of information in the string is very low, even though it's infinitely long. That is my definition of randomness, and it's (more or less) the author of this paper's definition. [0]: https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
    - throwawaymath 8y ago
      > Chapernowne's constant, 0.123456789101112... isn't "random" at all and contains very little information, yet it is known to be normal in base 10. Why is Chapernowne's constant not random? > The number would still have "infinite information" in the sense of the author of this paper. It would still be "just as random", it would still have "no pattern". But it would not be a normal number anymore. That's not true. It would not be just as random. If the set you're sampling from includes a 7 (i.e. the set of digits which can be represented in any single place in the sequence), and you never see a 7 for an extremely long time, this is exceptionally good heuristic evidence that the number is not random. And if we know 7 never shows up, we also know that the number is not random, because we know it's not uniformly sampling from the set of base 10 digits.

candiodari 8y ago

Okay, but 2 points: 1) Kolmogorov complexity is a measure of the computational resources needed to specify the object Depending on what you mean by "specify the object" this may or may not be infinite resources. My vote goes to infinite. Because you either need infinite resources even to just express this number, or you need infinite resources to actually run it. I get that you can create a finite program that gives an approximation of the number, but that's not the same, and only approximations can be finite. The number itself, and it's useful specifications, are all infinite. For the real number you need infinite resources to express it. So by what measure exactly does sqrt(2) have finite complexity ? In fact, you could use the old "every number occurs in Pi" trick and say that every other object is contained within it (and within every other real number), and since kolmogorov complexity is a metric I have just proven that the kolmogorov complexity of sqrt(2) is larger than any other kolmogorov complexity. The only number that satisfies that condition is infinite. 2) Even if this applies to the 4 numbers I specified, or the few thousand "well known" real numbers, it doesn't apply to any real proportion of real numbers. I mean, I can compute one or two 3rd degree boundary differential equations straight in my head, but that is very different from saying I can do that in the general case. Hell, quantum computers can't do it in the general case. The same is true for specifying real numbers. (and, more or less) 3) in reality, only approximations of sqrt(2) are computable. The real number itself isn't.