3 ms·
This is discussed heavily in topics around constructing the reals and constructivism. Wikipedia has a short section about using the computables instead of the r
by baddox 10y ago
This is discussed heavily in topics around constructing the reals and constructivism. Wikipedia has a short section about using the computables instead of the reals: https://en.m.wikipedia.org/wiki/Computable_number https://en.m.wikipedia.org/wiki/Computable_number
It is pretty fascinating to think about: that almost all real numbers are not computable ("almost all" of course meaning "all but a countable set"). And yet you almost certainly will never run into a noncomputable real except in computer science when you're specifically defining one to illustrate something about computability (like Chaitin's constant).
- IsaacL 10y agoAre there any good books on this topic?
- andybak 10y agoYes. An uncountable number are in the Library of Babel. (actually - I'm guessing there's actually a countable number in the Library of Babel but it didn't read quite so amusingly that way. In any case - all the ones I flicked through were trash.) Edit - The Library of Babel is actually finite isn't it? Fixed alphabet and fixed book length? It's a while since I read it.
- disconcision 10y agothe number of possible distinct books is finite but it's unknown if the library itself is finite. iirc it ended with the narrator speculating that, although the books themselves are devoid of meaning, perhaps the overall structure of the library is ordered, i.e. the same finite pattern of books repeats endlessly in infinite space.
- sn41 10y agoThe Library of Babel is finite if the books are unique. Interestingly, Borges does mention that one of the books in the library must be an index of the other books. This is similar to the notion of a universal computably enumerable language. However, I doubt that Borges' claim is accurate. If the set of programs is finite, then I think there cannot be a comprehensive index of all programs. A finite set is a regular language, and there is no universal regular language in the set of regular languages.
- philipov 10y agoI recommend Gregory Chaitin's book intended for a popular audience. It is short, and a good introduction to algorithmic information theory for non-mathematicians. Chaitin's Constant (Omega) is a non-computable number that is equivalent to the halting problem. [0]: https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/1400077974 https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/14...