3 ms·

corollary: Numberphile (with Matt Parker of Stand Up Maths) - "All the Numbers". Most are incomputable, of course :) [0] https://www.youtube.com/watch?v=5TkIe6

corollary: Numberphile (with Matt Parker of Stand Up Maths) - "All the Numbers". Most are incomputable, of course :) [0] https://www.youtube.com/watch?v=5TkIe60y2GI&t=1s https://www.youtube.com/watch?v=5TkIe60y2GI&t=1s

xscott 2y ago
Other than Chaitin's constant(s), name a few that aren't computable.
- nyrikki 2y ago
  Choose any arbitrarily small segment of the real line, all those numbers will be uncomputable almost everywhere While there are many (often equivalent) definitions of what a computable number are. And easy to grasp informal explanation is that a number is computable if you can write a function/algorithm f(n) such that it returns the n-th digit in a finite amount of time. For Pi as an example: f(3) = 4 (from 3.14) Almost all applies to the elements of an uncountable set except for countable subset. As the reals have a cardinality of 2^aleph_0 or aleph_1 (uncountable), but the Natural Numbers, Integers and Rationals are aleph_0 (countable), you have to find some many to one reduction. Chaitin's constant is uncomputable because it is effectively random, and no random problem is decidable, or (co)recursively enumerable) It gets mapped to the halting problem, because that is the canonical example but you could use the system identification problem, symbol-grounding problem, open frame problem etc.... But to answer your question, in the real interval [0,1], the computable numbers have measure zero, and the uncomputable numbers have measure one. So right there is an uncountable infinity of non-computable numbers.
  - immibis 2y ago
    Chaitin's constant is uncomputable because of its construction, not because it is "effectively random". Pi is also "effectively random".
    - nyrikki 2y ago
      π is a transcendental number meaning that it is not algebraic It is NOT an algorithmically random sequence. Chatlin's halting probability is normal, transcendental, and non-computable. https://arxiv.org/pdf/0904.1149 https://arxiv.org/pdf/0904.1149 > Chaitin [G. J. Chaitin, J. Assoc. Comput. Mach., vol. 22, pp. 329–340, 1975] introduced Ω number as a concrete example of random real. Being non-algebraic is not the same as being algorithmicly random in the formal sense.
    - bonoboTP 2y ago
      These are distinct senses of "random". Pi is conjectured (but not proven) to be a so-called normal number, which means that n-grams have uniform frequencies, so if you slide a window of size n over the digits, then every sequence of n digits will come up with equal frequency in the limit. Chaitin's omega is "random" in a stronger sense. There is no finite algorithm that can produce the digits. There's no compact, finite representation from which you could "unpack" those digits. The digits are what they are, the best way to represent them is simply to list them. Pi's digits are very "regular", but the pattern is not about repetitions in digits or skewed frequencies of certain digit sequences but that the digits follow from simple rules. A short program can generate those digits to arbitrary length. So in some sense they have redundancy, a kind of pattern to them.
  - xscott 2y ago
    I should've been more clear. The Reals are very unsettling because there are supposed to be so many of them, but nobody has used, named, or described more than a few which aren't computable. They are angels dancing on a pin which we've never seen and probably don't need for any of applied mathematics.
    - Tainnor 2y ago
      > and probably don't need for any of applied mathematics Basically everyone who uses mathematics in some applied capacity happily uses the real numbers.
      - xscott 2y ago
        No, all the numbers most anyone actually uses are computable, and it'd say something weird about determinism if they weren't. The word "need" was carrying some weight, as in necessary vs sufficient.
        Tainnor 2y ago
        It's not about individual numbers. Most applied maths fields (including physics) use the real numbers and the properties of real numbers as a complete field are implicitly assumed all the time (e.g. for differential equations). It's only ever some mathematicians, computer scientists and philosophers who care about the fact that most of them aren't computable. If you want to argue that one could derive a theory of physics etc. that doesn't rely on the real numbers that's one thing. That's probably possible although I doubt that it would be very elegant. But it's simply not what people use.
        xscott 2y ago
        > If you want to argue that one could derive a theory of physics etc. that doesn't rely on the real numbers that's one thing. That wasn't my original intent, but I think it's a legitimate stance. The Reals are bizarre (Banak Tarski, etc...), and we practically never use the non-computable ones. > It's only ever some mathematicians, computer scientists and philosophers who care about the fact that most of them aren't computable. Lol, who else WOULD care? :-) > That's probably possible although I doubt that it would be very elegant. That's an aesthetic judgment. Someone else might argue that sticking to the numbers we actually use and can calculate is simpler/cleaner/more elegant/whatever. And besides, I'm guessing you could replace ℝ with T (for Turing) and most of the proofs would go just fine. (Although the Computables have plenty of weirdness to them too...)

xscott 2y ago

Other than Chaitin's constant(s), name a few that aren't computable.

nyrikki 2y ago
Choose any arbitrarily small segment of the real line, all those numbers will be uncomputable almost everywhere While there are many (often equivalent) definitions of what a computable number are. And easy to grasp informal explanation is that a number is computable if you can write a function/algorithm f(n) such that it returns the n-th digit in a finite amount of time. For Pi as an example: f(3) = 4 (from 3.14) Almost all applies to the elements of an uncountable set except for countable subset. As the reals have a cardinality of 2^aleph_0 or aleph_1 (uncountable), but the Natural Numbers, Integers and Rationals are aleph_0 (countable), you have to find some many to one reduction. Chaitin's constant is uncomputable because it is effectively random, and no random problem is decidable, or (co)recursively enumerable) It gets mapped to the halting problem, because that is the canonical example but you could use the system identification problem, symbol-grounding problem, open frame problem etc.... But to answer your question, in the real interval [0,1], the computable numbers have measure zero, and the uncomputable numbers have measure one. So right there is an uncountable infinity of non-computable numbers.
- immibis 2y ago
  Chaitin's constant is uncomputable because of its construction, not because it is "effectively random". Pi is also "effectively random".
  - nyrikki 2y ago
    π is a transcendental number meaning that it is not algebraic It is NOT an algorithmically random sequence. Chatlin's halting probability is normal, transcendental, and non-computable. https://arxiv.org/pdf/0904.1149 https://arxiv.org/pdf/0904.1149 > Chaitin [G. J. Chaitin, J. Assoc. Comput. Mach., vol. 22, pp. 329–340, 1975] introduced Ω number as a concrete example of random real. Being non-algebraic is not the same as being algorithmicly random in the formal sense.
  - bonoboTP 2y ago
    These are distinct senses of "random". Pi is conjectured (but not proven) to be a so-called normal number, which means that n-grams have uniform frequencies, so if you slide a window of size n over the digits, then every sequence of n digits will come up with equal frequency in the limit. Chaitin's omega is "random" in a stronger sense. There is no finite algorithm that can produce the digits. There's no compact, finite representation from which you could "unpack" those digits. The digits are what they are, the best way to represent them is simply to list them. Pi's digits are very "regular", but the pattern is not about repetitions in digits or skewed frequencies of certain digit sequences but that the digits follow from simple rules. A short program can generate those digits to arbitrary length. So in some sense they have redundancy, a kind of pattern to them.
- xscott 2y ago
  I should've been more clear. The Reals are very unsettling because there are supposed to be so many of them, but nobody has used, named, or described more than a few which aren't computable. They are angels dancing on a pin which we've never seen and probably don't need for any of applied mathematics.
  - Tainnor 2y ago
    > and probably don't need for any of applied mathematics Basically everyone who uses mathematics in some applied capacity happily uses the real numbers.
    - xscott 2y ago
      No, all the numbers most anyone actually uses are computable, and it'd say something weird about determinism if they weren't. The word "need" was carrying some weight, as in necessary vs sufficient.
      - Tainnor 2y ago
        It's not about individual numbers. Most applied maths fields (including physics) use the real numbers and the properties of real numbers as a complete field are implicitly assumed all the time (e.g. for differential equations). It's only ever some mathematicians, computer scientists and philosophers who care about the fact that most of them aren't computable. If you want to argue that one could derive a theory of physics etc. that doesn't rely on the real numbers that's one thing. That's probably possible although I doubt that it would be very elegant. But it's simply not what people use.
        xscott 2y ago
        > If you want to argue that one could derive a theory of physics etc. that doesn't rely on the real numbers that's one thing. That wasn't my original intent, but I think it's a legitimate stance. The Reals are bizarre (Banak Tarski, etc...), and we practically never use the non-computable ones. > It's only ever some mathematicians, computer scientists and philosophers who care about the fact that most of them aren't computable. Lol, who else WOULD care? :-) > That's probably possible although I doubt that it would be very elegant. That's an aesthetic judgment. Someone else might argue that sticking to the numbers we actually use and can calculate is simpler/cleaner/more elegant/whatever. And besides, I'm guessing you could replace ℝ with T (for Turing) and most of the proofs would go just fine. (Although the Computables have plenty of weirdness to them too...)