MathOverflow is a question and answer site for professional mathematicians. It's built and run by you as part of the Stack Exchange network of Q&A sites. With your help, we're working together to build a library of detailed answers to every question about research level mathematics.
We're a little bit different from other sites. Here's how:
This site is all about getting answers. It's not a discussion forum. There's no chit-chat.
Just questions...
...and answers.
Good answers are voted up and rise to the top.
The best answers show up first so that they are always easy to find.
The person who asked can mark one answer as "accepted".
Accepting doesn't mean it's the best answer, it just means that it worked for the person who asked.
I've been looking for a full, detailed proof that Chaitin's constant is incompressible, i.e. there is a universal constant $c$ such that every program writing first $n$ digits of $\Omega$ has length at least $n-c$. I wasn't able to find such detailed proof, so I'm asking this question.
Thanks in advance!
This is in Downey and Hirschfeldt: Algorithmic randomness and complexity, Theorem 6.1.3, which cites
Chaitin, G. Information-theoretical characterizations of recursive infinite strings, Theoretical Computer Science, vol. 2 (1976), 45-48.
See Chaitin's very illuminating book http://arxiv.org/abs/math/0404335 (Meta Math! The Quest for Omega).
Focus on questions about an actual problem you have faced. Include details about what you have tried and exactly what you are trying to do.
Ask about...
Not all questions work well in our format. Avoid questions that are primarily opinion-based, or that are likely to generate discussion rather than answers.
Questions that need improvement may be closed until someone fixes them.
Don't ask about...
All questions are tagged with their subject areas. Each can have up to 5 tags, since a question might be related to several subjects.
Click any tag to see a list of questions with that tag, or go to the tag list to browse for topics that interest you.
I've been looking for a full, detailed proof that Chaitin's constant is incompressible, i.e. there is a universal constant $c$ such that every program writing first $n$ digits of $\Omega$ has length at least $n-c$. I wasn't able to find such detailed proof, so I'm asking this question.
Thanks in advance!
Your reputation score goes up when others vote up your questions, answers and edits.
As you earn reputation, you'll unlock new privileges like the ability to vote, comment, and even edit other people's posts.
| Reputation | Privilege |
|---|---|
| 15 | Vote up |
| 50 | Leave comments |
| 125 | Vote down (costs 1 rep on answers) |
At the highest levels, you'll have access to special moderation tools. You'll be able to work alongside our community moderators to keep the site focused and helpful.
| 2000 | Edit other people's posts |
|---|---|
| 3000 | Vote to close, reopen, or migrate questions |
| 10000 | Access to moderation tools |
Our goal is to have the best answers to every question, so if you see questions or answers that can be improved, you can edit them.
Use edits to fix mistakes, improve formatting, or clarify the meaning of a post.
This is in Downey and Hirschfeldt: Algorithmic randomness and complexity, Theorem 6.1.3, which cites
Chaitin, G. Information-theoretical characterizations of recursive infinite strings, Theoretical Computer Science, vol. 2 (1976), 45-48.
Badges are special achievements you earn for participating on the site. They come in three levels: bronze, silver, and gold.
| Student | Asked first question with score of 1 or more |
| Editor | First edit |
| Good Answer | Answer score of 25 or more |
| Civic Duty | Voted 300 or more times |
| Famous Question | Asked a question with 10,000 views |
Like this site? Stack Exchange is a network of 127 Q&A sites just like it. Check out the full list of sites.
Use comments to ask for more information or clarify a question or answer.
You can always comment on your own questions and answers. Once you earn 50 reputation, you can comment on anybody's post.
Remember: we're all here to learn, so be friendly and helpful!