4 ms·

Consider the set of all real numbers which you can actually specify IN ANY FASHION AT ALL, so that the person writing a paper about it and the person reading th

by mcherm 10y ago

Consider the set of all real numbers which you can actually specify IN ANY FASHION AT ALL, so that the person writing a paper about it and the person reading the paper are talking about the same number. This includes easy ones like "3" or "Square root of Pi". It includes oddballs like Chaitin's constant -- the probability that a randomly constructed program will not get stuck in an infinite loop (for some particular choice of computer and programming language) -- which is so ornery a number that we cannot (even in THEORY) figure out a single digit of it (other than its being between 0 and 1). Consider that great big set. It's still countable. The thing that makes "real numbers" bigger than integers, the "extra" that real numbers have must be very, very peculiar.

GregBuchholz 10y ago
>Chaitin's constant -- <snip> -- which is so ornery a number that we cannot (even in THEORY) figure out a single digit of it (other than its being between 0 and 1). You might be interested in: https://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf https://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf "A Chaitin Omega number is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Omega number is both computably enumerable (the limit of a computable, increasing, converging sequence of rationals) and random(its binary expansion is an algorithmic random sequence). In particular, every Omega number is strongly noncomputable. The aim of this paper is to describe a procedure, that combines Java programming and mathematical proofs, to compute the exact values of the first 64 bits of a Chaitin Omega: 0000001000000100000110001000011010001111110010111011101000010000"
- tromp 10y ago
  Unfortunately, that is not a Chaitin Omega, since the notion of program length in that paper is flawed. In particular, it counts a 0 or a 1 provided as binary data in the program as adding 7 bits of length to the program. Later papers by Calude fix this problem, while reducing the number of computed bits to 43.
stymaar 10y ago
> Consider that great big set. It's still countable. You didn't prove that statement, and actually Cantor's diagonal arguments [1] proves you wrong: Consider the set of «all real numbers which you can actually specify IN ANY FASHION AT ALL». If you can count it, you can order them in a certain fashion: n0, n1, n2, n3 … It's easy to specify a number X which is not part of this set (which is in contradiction with the definition of this set, and demonstrates ad absurdum that this set is not countable). To build such X, consider the n-th decimal of the n-th number: if it's zero, the n-th decimal of X is 1, otherwise the n-th decimal is 0. Then by construction, X is different from any number of this set, which mean X is not a part of the set. □ [1]: https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
- gertef 10y ago
  The number you are paraphrasing cannot be precisely identified in finite time.
  - stymaar 10y ago
    Oh, you're right. For that I would need to explicit the construction of the sequence n0, n1, … but that's impossible : if I can find such sequence, my proof holds but at the same time such sequence shows that the set is countable => contradiction, hence there is no such sequence. But well, now that we've proven that such sequence doesn't exist, we've proven that the given set is not countable ! Not the most elegant proof ever, but I think it works.
    - stymaar 10y ago
      Actually it doesn't: what if the given sequence exists but cannot be expressed with words ? (This is exactly the same thing than «a real number that can't ne expressed with words» which is what I'm trying to demonstrate not to exist. I'm going nowhere)
- moefh 10y ago
  I don't think that argument works. How do you guarantee that you can compute the n-th decimal of the n-th number in the list? In fact, from what I understand, this paper[1] shows how to specify exactly a number can't be computed like that. [1] https://arxiv.org/pdf/1003.0480.pdf https://arxiv.org/pdf/1003.0480.pdf
deepsun 10y ago
What about phrases that specify some numbers on Thursdays, and another numbers when Moon is in second quarter? What about phrases that some people agree specifies a number, while other people think it's another number, and yet another people just aren't sure? What about phrases that specify one and the same number for a specific person, but once that person reached age of 40, then he/she is not sure anymore? I just making counter-examples to Jules Richard paradox formulation, showing that it's not properly formalized, but rather expressed in vague language, so cannot be considered strict mathematics.
- E6300 10y ago
  > What about phrases that specify some numbers on Thursdays, and another numbers when Moon is in second quarter? Would you mind producing such a phrase? > What about phrases that some people agree specifies a number, while other people think it's another number, and yet another people just aren't sure? > What about phrases that specify one and the same number for a specific person, but once that person reached age of 40, then he/she is not sure anymore? You may as well ask whether someone understanding a theorem has any bearing on its truth value. A well-formed sentence in a formal language has one and only one meaning regardless of whether a specific person understands it. That's the whole point of using a formal language. If meaning is actually somehow bound to its interpretation then communication of even the simplest of mathematics is totally impossible.
  - deepsun 10y ago
    > Would you mind producing such a phrase? Sure: "Current quarter of the Moon". Or "How Giants scored last season". Or "One, if P=NP, zero otherwise". Well, I see your point, if we limit our phrases to only formal language, then you're right.
    - E6300 10y ago
      > "Current quarter of the Moon". Or "How Giants scored last season" These sentences describe functions, not numbers. > "One, if P=NP, zero otherwise". This value is a constant. It doesn't change through time. We simply don't know what it is.

by mcherm 10y ago

GregBuchholz 10y ago

>Chaitin's constant -- <snip> -- which is so ornery a number that we cannot (even in THEORY) figure out a single digit of it (other than its being between 0 and 1). You might be interested in: https://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf https://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf "A Chaitin Omega number is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Omega number is both computably enumerable (the limit of a computable, increasing, converging sequence of rationals) and random(its binary expansion is an algorithmic random sequence). In particular, every Omega number is strongly noncomputable. The aim of this paper is to describe a procedure, that combines Java programming and mathematical proofs, to compute the exact values of the first 64 bits of a Chaitin Omega: 0000001000000100000110001000011010001111110010111011101000010000"

tromp 10y ago
Unfortunately, that is not a Chaitin Omega, since the notion of program length in that paper is flawed. In particular, it counts a 0 or a 1 provided as binary data in the program as adding 7 bits of length to the program. Later papers by Calude fix this problem, while reducing the number of computed bits to 43.

stymaar 10y ago

> Consider that great big set. It's still countable. You didn't prove that statement, and actually Cantor's diagonal arguments [1] proves you wrong: Consider the set of «all real numbers which you can actually specify IN ANY FASHION AT ALL». If you can count it, you can order them in a certain fashion: n0, n1, n2, n3 … It's easy to specify a number X which is not part of this set (which is in contradiction with the definition of this set, and demonstrates ad absurdum that this set is not countable). To build such X, consider the n-th decimal of the n-th number: if it's zero, the n-th decimal of X is 1, otherwise the n-th decimal is 0. Then by construction, X is different from any number of this set, which mean X is not a part of the set. □ [1]: https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

gertef 10y ago
The number you are paraphrasing cannot be precisely identified in finite time.
- stymaar 10y ago
  Oh, you're right. For that I would need to explicit the construction of the sequence n0, n1, … but that's impossible : if I can find such sequence, my proof holds but at the same time such sequence shows that the set is countable => contradiction, hence there is no such sequence. But well, now that we've proven that such sequence doesn't exist, we've proven that the given set is not countable ! Not the most elegant proof ever, but I think it works.
  - stymaar 10y ago
    Actually it doesn't: what if the given sequence exists but cannot be expressed with words ? (This is exactly the same thing than «a real number that can't ne expressed with words» which is what I'm trying to demonstrate not to exist. I'm going nowhere)
moefh 10y ago
I don't think that argument works. How do you guarantee that you can compute the n-th decimal of the n-th number in the list? In fact, from what I understand, this paper[1] shows how to specify exactly a number can't be computed like that. [1] https://arxiv.org/pdf/1003.0480.pdf https://arxiv.org/pdf/1003.0480.pdf

deepsun 10y ago

What about phrases that specify some numbers on Thursdays, and another numbers when Moon is in second quarter? What about phrases that some people agree specifies a number, while other people think it's another number, and yet another people just aren't sure? What about phrases that specify one and the same number for a specific person, but once that person reached age of 40, then he/she is not sure anymore? I just making counter-examples to Jules Richard paradox formulation, showing that it's not properly formalized, but rather expressed in vague language, so cannot be considered strict mathematics.

E6300 10y ago
> What about phrases that specify some numbers on Thursdays, and another numbers when Moon is in second quarter? Would you mind producing such a phrase? > What about phrases that some people agree specifies a number, while other people think it's another number, and yet another people just aren't sure? > What about phrases that specify one and the same number for a specific person, but once that person reached age of 40, then he/she is not sure anymore? You may as well ask whether someone understanding a theorem has any bearing on its truth value. A well-formed sentence in a formal language has one and only one meaning regardless of whether a specific person understands it. That's the whole point of using a formal language. If meaning is actually somehow bound to its interpretation then communication of even the simplest of mathematics is totally impossible.
- deepsun 10y ago
  > Would you mind producing such a phrase? Sure: "Current quarter of the Moon". Or "How Giants scored last season". Or "One, if P=NP, zero otherwise". Well, I see your point, if we limit our phrases to only formal language, then you're right.
  - E6300 10y ago
    > "Current quarter of the Moon". Or "How Giants scored last season" These sentences describe functions, not numbers. > "One, if P=NP, zero otherwise". This value is a constant. It doesn't change through time. We simply don't know what it is.