6 ms·

Hey, non-mathematician computer science type here. If I follow correctly, the issue with randomly picking any real number in that interval is that irrational n

Hey, non-mathematician computer science type here. If I follow correctly, the issue with randomly picking any real number in that interval is that irrational numbers would require infinite computational steps to resolve. So the probability is really 0 that you'll get an irrational. If you have a finite number of computations, you're guaranteed to resolve to a rational, while if you have an infinite number of computations, you never resolve to anything. Is that a decent lay interpretation?

aportnoy 8y ago
The opposite is true. Take the interval [0, 1], "sample a random real number x" from it. P(x is rational) = 0, P(x is irrational) = 1. Informally, the overwhelming majority of real numbers are irrational.
- mavhc 8y ago
  What's weird is there's always a rational number between any 2 irrational numbers, yet there are way more irrational numbers
  - lisper 8y ago
    All this becomes pretty intuitive if you think about numbers in terms of their decimal expansions. A "random number" is one with a random digit in each of its (infinitely long) list of decimal digits. A rational number is one where, at some finite point, all of the digits start to repeat in some finite pattern. The odds of that happening by chance are zero. Likewise, if you take any two randomly generated list of decimal digits, at some point there will be a digit in the same place that is different between the two. At that point, you can construct a rational between the two by choosing the smaller digit and then adding "1000....". But yeah, it's kind of weird.
  - thaumasiotes 8y ago
    Corollary: rational numbers must serve double duty separating many different pairs of irrational numbers. You can keep going with things that sound weird: There are infinitely many rationals between any two irrational numbers. There are as many rational numbers between any two finite irrational numbers as there are between positive and negative infinity.
    - throwawaymath 8y ago
      Can you clarify that last point? I don't think it's strictly true. Aside from countable and uncountable infinities, you can have larger and smaller infinites as well. Unless every set S of all rational numbers between any irrational x and irrational y is isomorphic to the set P of all rational numbers, I don't see that this is correct. And I don't immediately see that you can put them into 1-1 correspondence.
      - zeeboo 8y ago
        Do you agree both sets are countable? If so, any two countable sets can be put into bijection by composing their bijections to the naturals.
        throwawaymath 8y ago
        Oh, right. Yeah I guess that makes sense by definition.
      - aportnoy 8y ago
        Any infinite set is either countable or uncountable.
        throwawaymath 8y ago
        I'm aware, but that's not what I meant.
gpm 8y ago
Uniformly at random picking a number from the interval [0, 1] isn't possible with a turing machine (even giving it access to random coins). I.e. it's not a computable function. It doesn't even really make sense, you can't represent uncountably many numbers on a turing machine, so it isn't even possible to return all but a tiny subset of the space. You're imagining some turing machine that attempts to compute it anyways and thinking about the output. You seem to think that you can make a turing machine that - In the probability 0 case that we should output a rational, will output that number - Will otherwise infinite loop This is randomized, so we are getting our randomness from some kind of "coin flip" like process. To know that we are in the that probability 0 case of outputting a rational, we will need to have seen infinitely many coin flips. If we've seen only n coin flips, there is still 1/2^n > 0 of the probability space that we haven't explored. So in fact any such turing machine has to loop infinitely in the rational case as well.
- man-and-laptop 8y ago
  Replace the role of Turing Machines with Type 2 Turing Machines. Then it is possible. And it's got absolutely nothing to do with computable functions. [edit] The downvoters can't argue with facts. I am not deleting this comment.
  - gpm 8y ago
    Computers are not type 2 turing machines, nor are any other physically existing thing that we know of. They aren't really turing machines either because they have a finite tape, but since we are only interested in running the turing machine for a finite amount of time and thus accessing a finite amount of tape that distinction is unimportant. The standard definition of computable is on a turing machine, not a type 2 turing machine. Of course we can define an alternate model where more things are computable. Edit: And the standard definition of computable is relevant because it happens to be the exact set of functions we can compute on real computers. While Weihrauch [0] does introduce a different definition of the word computable, that would in a randomized setting allow for sampling from the interval [0, 1] (and not just for rationals as I understand it either). Any algorithm on his "oracle turing machines" will still have to take an infinite amount of time, even to return the rationals. He just allows that in his definition of computable. [0] https://core.ac.uk/download/pdf/82440448.pdf https://core.ac.uk/download/pdf/82440448.pdf
mcphage 8y ago
> If I follow correctly, the issue with randomly picking any real number in that interval is that irrational numbers would require infinite computational steps to resolve. In mathematics, doing things an infinite number of times is generally no problem, in fact it’s almost always done. Of course, there are also many different sizes of infinity, and doing things a larger infinite size number of times requires some extra steps... but most branches of math only do things a countable infinite number of times (the smallest infinity).
Viliam1234 8y ago
"Rational" numbers are those that can be expressed as a fraction of two integers. For example, a square root of two is not rational. "Computable" numbers are those that can be calculated by a computer (with unlimited memory, but finite speed) with arbitrary (not infinite) precision in finite time. As a rule of thumb, anything you can express using words like "plus", "minus", "square root", "logarithm" etc. is going to be computable. > irrational numbers would require infinite computational steps to resolve No, this is not the real reason. Both "1/3" and "square root of 2" have infinite number of decimal places, so neither can be fully written by a computer program. However, each of them can be approximated to e.g. one billion decimal places. To show you how most numbers are not rational, consider only numbers of form "A + B * square root of two", where A and B are rational. Each different pair of A and B gives you a unique number. Among them, the numbers with B = zero are rational, and numbers with B <> zero are irrational. (Furthermore, all rational numbers can be expressed like this, but many irrational numbers, such as "square root of three" are outside of this set.) This should make it intuitively obvious why a randomly picked number is infinitely unlikely to be rational. But the rabbit hole goes much deeper. Let's ignore all technical details, and take a set of all numbers you can describe (unambiguously, and without any paradox) by a sentence of a finite length (including any finite number of equations of a finite length). If you need a whole book to define a number, so be it. Take all numbers humans can describe. The point is that all these numbers are just an infinite minority in the vast ocean of real numbers. How can that be? What else is missing? This seems tricky, because -- by definition -- I should be unable to give you an example of a number that cannot be described. But even if I can't give you a specific number, I can point you towards a concept: the numbers whose decimal digits are all randomly generated. Any number that can be described by a finite description, contains a finite amount of information. A number with infinitely many randomly generated digits contains an infinite amount of information. To put it differently, when you generate numbers with infinite number of random decimal digits, you would have to be infinitely lucky to generate a number which only happens to contain a finite amount of information (for example, when all randomly generated digits happen to be zeroes). But the former are the real numbers, and the latter are the computable numbers. So if you take a random real number, you have to be infinitely lucky to get a computable one. There is actually more, because "infinitely more" does not adequately describe the difference between comparing "rational" with "irrational, but still computable" numbers (both infinities have the same cardinality), and "computable" with "real" numbers (infinities of a different cardinality)... but this part, I am afraid, is beyond lay interpretations and requires paying attention to some technical definitions. A simple version is that the rational numbers and the computable numbers can both be numbered by integers, if we choose a sufficiently smart numbering scheme; but for real numbers, even this is impossible. But it takes some technical details to explain why it is so, and why it matters so much.

aportnoy 8y ago

The opposite is true. Take the interval [0, 1], "sample a random real number x" from it. P(x is rational) = 0, P(x is irrational) = 1. Informally, the overwhelming majority of real numbers are irrational.

mavhc 8y ago
What's weird is there's always a rational number between any 2 irrational numbers, yet there are way more irrational numbers
- lisper 8y ago
  All this becomes pretty intuitive if you think about numbers in terms of their decimal expansions. A "random number" is one with a random digit in each of its (infinitely long) list of decimal digits. A rational number is one where, at some finite point, all of the digits start to repeat in some finite pattern. The odds of that happening by chance are zero. Likewise, if you take any two randomly generated list of decimal digits, at some point there will be a digit in the same place that is different between the two. At that point, you can construct a rational between the two by choosing the smaller digit and then adding "1000....". But yeah, it's kind of weird.
- thaumasiotes 8y ago
  Corollary: rational numbers must serve double duty separating many different pairs of irrational numbers. You can keep going with things that sound weird: There are infinitely many rationals between any two irrational numbers. There are as many rational numbers between any two finite irrational numbers as there are between positive and negative infinity.
  - throwawaymath 8y ago
    Can you clarify that last point? I don't think it's strictly true. Aside from countable and uncountable infinities, you can have larger and smaller infinites as well. Unless every set S of all rational numbers between any irrational x and irrational y is isomorphic to the set P of all rational numbers, I don't see that this is correct. And I don't immediately see that you can put them into 1-1 correspondence.
    - zeeboo 8y ago
      Do you agree both sets are countable? If so, any two countable sets can be put into bijection by composing their bijections to the naturals.
      - throwawaymath 8y ago
        Oh, right. Yeah I guess that makes sense by definition.
    - aportnoy 8y ago
      Any infinite set is either countable or uncountable.
      - throwawaymath 8y ago
        I'm aware, but that's not what I meant.

gpm 8y ago

Uniformly at random picking a number from the interval [0, 1] isn't possible with a turing machine (even giving it access to random coins). I.e. it's not a computable function. It doesn't even really make sense, you can't represent uncountably many numbers on a turing machine, so it isn't even possible to return all but a tiny subset of the space. You're imagining some turing machine that attempts to compute it anyways and thinking about the output. You seem to think that you can make a turing machine that - In the probability 0 case that we should output a rational, will output that number - Will otherwise infinite loop This is randomized, so we are getting our randomness from some kind of "coin flip" like process. To know that we are in the that probability 0 case of outputting a rational, we will need to have seen infinitely many coin flips. If we've seen only n coin flips, there is still 1/2^n > 0 of the probability space that we haven't explored. So in fact any such turing machine has to loop infinitely in the rational case as well.

man-and-laptop 8y ago
Replace the role of Turing Machines with Type 2 Turing Machines. Then it is possible. And it's got absolutely nothing to do with computable functions. [edit] The downvoters can't argue with facts. I am not deleting this comment.
- gpm 8y ago
  Computers are not type 2 turing machines, nor are any other physically existing thing that we know of. They aren't really turing machines either because they have a finite tape, but since we are only interested in running the turing machine for a finite amount of time and thus accessing a finite amount of tape that distinction is unimportant. The standard definition of computable is on a turing machine, not a type 2 turing machine. Of course we can define an alternate model where more things are computable. Edit: And the standard definition of computable is relevant because it happens to be the exact set of functions we can compute on real computers. While Weihrauch [0] does introduce a different definition of the word computable, that would in a randomized setting allow for sampling from the interval [0, 1] (and not just for rationals as I understand it either). Any algorithm on his "oracle turing machines" will still have to take an infinite amount of time, even to return the rationals. He just allows that in his definition of computable. [0] https://core.ac.uk/download/pdf/82440448.pdf https://core.ac.uk/download/pdf/82440448.pdf

mcphage 8y ago

> If I follow correctly, the issue with randomly picking any real number in that interval is that irrational numbers would require infinite computational steps to resolve. In mathematics, doing things an infinite number of times is generally no problem, in fact it’s almost always done. Of course, there are also many different sizes of infinity, and doing things a larger infinite size number of times requires some extra steps... but most branches of math only do things a countable infinite number of times (the smallest infinity).

Viliam1234 8y ago

"Rational" numbers are those that can be expressed as a fraction of two integers. For example, a square root of two is not rational. "Computable" numbers are those that can be calculated by a computer (with unlimited memory, but finite speed) with arbitrary (not infinite) precision in finite time. As a rule of thumb, anything you can express using words like "plus", "minus", "square root", "logarithm" etc. is going to be computable. > irrational numbers would require infinite computational steps to resolve No, this is not the real reason. Both "1/3" and "square root of 2" have infinite number of decimal places, so neither can be fully written by a computer program. However, each of them can be approximated to e.g. one billion decimal places. To show you how most numbers are not rational, consider only numbers of form "A + B * square root of two", where A and B are rational. Each different pair of A and B gives you a unique number. Among them, the numbers with B = zero are rational, and numbers with B <> zero are irrational. (Furthermore, all rational numbers can be expressed like this, but many irrational numbers, such as "square root of three" are outside of this set.) This should make it intuitively obvious why a randomly picked number is infinitely unlikely to be rational. But the rabbit hole goes much deeper. Let's ignore all technical details, and take a set of all numbers you can describe (unambiguously, and without any paradox) by a sentence of a finite length (including any finite number of equations of a finite length). If you need a whole book to define a number, so be it. Take all numbers humans can describe. The point is that all these numbers are just an infinite minority in the vast ocean of real numbers. How can that be? What else is missing? This seems tricky, because -- by definition -- I should be unable to give you an example of a number that cannot be described. But even if I can't give you a specific number, I can point you towards a concept: the numbers whose decimal digits are all randomly generated. Any number that can be described by a finite description, contains a finite amount of information. A number with infinitely many randomly generated digits contains an infinite amount of information. To put it differently, when you generate numbers with infinite number of random decimal digits, you would have to be infinitely lucky to generate a number which only happens to contain a finite amount of information (for example, when all randomly generated digits happen to be zeroes). But the former are the real numbers, and the latter are the computable numbers. So if you take a random real number, you have to be infinitely lucky to get a computable one. There is actually more, because "infinitely more" does not adequately describe the difference between comparing "rational" with "irrational, but still computable" numbers (both infinities have the same cardinality), and "computable" with "real" numbers (infinities of a different cardinality)... but this part, I am afraid, is beyond lay interpretations and requires paying attention to some technical definitions. A simple version is that the rational numbers and the computable numbers can both be numbered by integers, if we choose a sufficiently smart numbering scheme; but for real numbers, even this is impossible. But it takes some technical details to explain why it is so, and why it matters so much.