5 ms·
The key phrases there are "almost surely" and "most irrational numbers." There are irrational numbers like pi which can be defined algorithmically, but taken to
by mag487 13y ago
The key phrases there are "almost surely" and "most irrational numbers." There are irrational numbers like pi which can be defined algorithmically, but taken together as a set they have zero Lebesgue measure. (In fact, they're countable.)
- nawitus 13y agoI didn't know that. Any link to a proof?
- nwhitehead 13y agoConsider the set P of programs that take no input and generate an infinite stream of digits. Each program in P has a finite length and is written out of a finite set of symbols, so there must only be a finite number of programs of any given length. That makes P countable. Let Q be the set of numbers described by programs in P. Each program from P describes exactly one number, so Q must also be countable. The set of irrational numbers is uncountable, so there must be an uncountable set of "complex" irrational numbers remaining after you take away all the "non complex" ones in Q.
- nawitus 13y agoYour proof seems to only prove that a finite number of programs (described by you) which can produce a finite number of irrational numbers, while there are infinite number of irrational numbers. But we're surely not talking about a finite number of programs. I'm not even sure what the Kolmogorov complexity of a "complex irrational number" means. If you need the sequence of digits and you cannot use an algorithm to produce the digits, then the complexity is infinite?
- consz 13y agoThe set of irrational numbers which can be defined algorithmically are programable, eg. they are defined by a program of finite length.
- hollerith 13y ago>The set of irrational numbers which can be defined algorithmically are programable You mean "computable".
- nwhitehead 13y agoFor each fixed length there are a finite number of programs of that length. If we use 8-bit bytes for the alphabet, there are 256^N programs of length N. The set of ALL programs is infinite (we don't limit the length of programs), but it is countable. The "countable" part means we can put the set into one-to-one correspondence with the natural numbers. The correspondence starts with 0 mapping to the empty program, then 1-256 mapping to programs of a single byte, then 257-65793 mapping to the programs of two bytes, and so on. This mapping will hit each program exactly once, and it will hit every program because every individual program has a finite length. Different types of infinities are not intuitive so don't feel bad if the concepts are confusing. These issues troubled lots of very smart mathematicians for decades. The existence of irrational numbers was hugely troubling to Pythagoreans. The existence of uncountable infinities discovered by Cantor was shocking [1]. [1]: http://en.wikipedia.org/wiki/Controversy_over_Cantor%27s_theory http://en.wikipedia.org/wiki/Controversy_over_Cantor%27s_the...
- mtdewcmu 13y agoIn some sense, the existence of irrational numbers with no pattern in their digits is an illusory artifact of the number system. We can talk about them collectively because decimals are not required to have an end, and we have to postulate them to fill in the gaps in the number line, but such numbers lack any description or means of being separated as individuals. But then, is any mathematical abstraction real? I guess it's all beside the point.
- phaemon 13y agoThis is wrong. The square root of two was identified as irrational by the ancient Greeks, when considering the length of the diagonal of the unit square. The proof has nothing to do with decimal fractions (they didn't use decimal fractions at all).
- mtdewcmu 13y agoI'm referring to irrational numbers with no pattern. Square roots can be described and the digits can be enumerated by an algorithm. The diagonalization argument shows that there can't be a description for all irrational numbers.
- mag487 13y agoThere's only a countable number of formulas of ZFC. Therefore, there's only a countable number ways of writing out a formula of ZFC that uniquely specifies a real number. Therefore, only countably many real numbers exist that have such definitions. And all countable sets of reals have zero Lebesgue measure.
- nawitus 13y agoAdditional question: what's the Kolmogorov complexity of a irrational numberwhich is not described with a ZFC formula? And how is it described?
- mag487 13y agoI haven't really studied algorithmic information theory, but I'd assume that Kolmogorov complexity isn't defined for uncomputable/undefinable numbers. Or maybe it's defined as "infinite," but either way, my guess is that such numbers are simply ignored. (Interestingly, the function which takes a computable number and outputs its Kolmogorov complexity is itself uncomputable!)
- nawitus 13y agoThe article at least implies that the Kolmogorov complexity of uncomputable irrational numbers is larger than computable irrational numbers.