3 ms·

> which itself [uncomputable numbers] is the most intuitive way to define uncountable sets Can you explain your intuition for this step?

mFixman 7y ago
One of the ways to define the set of computable numbers is as the set of numbers for which there exists a program that, given an integer, gives you the n'th digit of this number. This set is countable: each one of these programs represents a single number, and you can use Gauss to transform any program into a integer and vice-versa. What's amazing is that almost every real number you heard about is part of this set: pi, e, and √2 can all be nicely put into a well-defined countable set. The set of the reals is uncountable, which means that almost every number is uncomputable like Chaitin's constant.
- frutiger 7y ago
  You have described how the set of computable numbers are countable. But you have then posited "the set of the reals is uncountable" without any further explanation as to how that is the case. Your explanation helps one understand why computable numbers are countable (and that is for sure a useful insight), but says nothing about uncountable sets. I still feel the diagonal argument is the clearest intuition for defining an uncountable set.
  - mFixman 7y ago
    I was taught that real numbers were countable before learning what computables numbers where. "There's a set of countable numbers that includes every real number you know and doesn't include handwavy concepts" was news to me. Personally, I never found the diagonal argument intuitive. The proof with the nested open intervals in a sequence was easier for me to understand, but that's probably because I have more of a background in CS.
- yongjik 7y ago
  Just a second, that's technically true, but the set of all "uncomputable but definable(?)" numbers is also countable, which includes Chaitin's constant (and any uncomputable number that can be reasonably called "X's constant"). Almost every real number is not only not computable, they aren't even definable.

mFixman 7y ago

One of the ways to define the set of computable numbers is as the set of numbers for which there exists a program that, given an integer, gives you the n'th digit of this number. This set is countable: each one of these programs represents a single number, and you can use Gauss to transform any program into a integer and vice-versa. What's amazing is that almost every real number you heard about is part of this set: pi, e, and √2 can all be nicely put into a well-defined countable set. The set of the reals is uncountable, which means that almost every number is uncomputable like Chaitin's constant.

frutiger 7y ago
You have described how the set of computable numbers are countable. But you have then posited "the set of the reals is uncountable" without any further explanation as to how that is the case. Your explanation helps one understand why computable numbers are countable (and that is for sure a useful insight), but says nothing about uncountable sets. I still feel the diagonal argument is the clearest intuition for defining an uncountable set.
- mFixman 7y ago
  I was taught that real numbers were countable before learning what computables numbers where. "There's a set of countable numbers that includes every real number you know and doesn't include handwavy concepts" was news to me. Personally, I never found the diagonal argument intuitive. The proof with the nested open intervals in a sequence was easier for me to understand, but that's probably because I have more of a background in CS.
yongjik 7y ago
Just a second, that's technically true, but the set of all "uncomputable but definable(?)" numbers is also countable, which includes Chaitin's constant (and any uncomputable number that can be reasonably called "X's constant"). Almost every real number is not only not computable, they aren't even definable.