4 ms·
My Favorite Strange Number: Ω
- JonnieCache 15y agoThis is discussed in the following google Tech Talk, "Incompleteness: a personal perspective" from Cristian Claude http://www.youtube.com/watch?v=tYjmiT422yQ http://www.youtube.com/watch?v=tYjmiT422yQ He discusses, amongst other things, the work done on computing this uncomputable number, and why that isn't a contradiction. I think one of the people involved is in the audience.
- kzrdude 15y agoThe link to Calude's paper in the article is broken, it is this: http://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf http://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf
- deleted 15y ago[deleted]
- deleted 15y ago[deleted]
- deleted 15y ago[deleted]
- Symmetry 15y agoAnd oddly enough, one of my favorite numbers is the Ω of S=k*ln(Ω) fame. http://en.wikipedia.org/wiki/Microcanonical_ensemble http://en.wikipedia.org/wiki/Microcanonical_ensemble
- ced 15y agoI don't understand how omega can be be incompressible. Compression, from the information theory perspective, allows me to send the string Digits #10000 to #100000 of the decimal representation of omega. which any competent human could "decompress" into the corresponding digit sequence (inasmuch as it's computable)
- gjm11 15y agoThe bit in parentheses is why your argument doesn't show that omega isn't incompressible: it very emphatically isn't computable.
- ced 15y agoYeah, but compression is all about communicating information. If I don't have the information that I want to communicate, it's weird to claim that it's incompressible. Are the lost works of Shakespeare incompressible because we can't know what they contained? That's a meaningless statement to me. Besides, some of the bits are known, and thus, they are clearly compressible.
- andrewcooke 15y agoyou're right that the isolated assertion is not at all sensible, but the wider context is that you are considering all possible algorithms and the sequences that they generate, and looking for some way of compressing as many of those as possible. you should read one of chaitin's books for a better idea (they're generally "accessible", but at some point you just give up trying to make complete sense of it all...) in other words, you are choosing your compression for one particular algorithm (the one that generates omega - you could go further and say it's 1 for omega and 0 for everything else). this is a common problem in arguments about compressibility (if we're only trying to compress beethoven's ninth then i can do that in one bit too) - you have to be talking in an "average" or statistical sense for things to be useful. having said that, the exact nature of what they're saying is still not clear to me (ie it's not clear exactly how the details of the argument work out, or how this eventually ties back to http://en.wikipedia.org/wiki/Shannons_source_coding_theorem http://en.wikipedia.org/wiki/Shannons_source_coding_theorem).
- andrewcooke 15y agoi think another replier here may also be correct that chaitin, in particular, includes the length of the decompression code. unfortunately i can't delete my answer for some reason (too old i guess).
- sehugg 15y agoDifferent but related -- The busy beaver game and the Σ function: http://en.wikipedia.org/wiki/Busy_beaver http://en.wikipedia.org/wiki/Busy_beaver
- doodyhead 15y agoThe Halting Problem theoretically defines the limits of computation, but has anyone in a pragmatic, everyday coding situation actually reached that limit? In the practical sense I've never seen it have any bearing. Perhaps the problems I'm working on are too mundane.
- khafra 15y agoI had just remarked, the other day, that people obsessed with Chaitin's Omega are much more interesting than people obsessed with Pi.