For example, Chaitin's constant is both Martin-Löf random and uncomputable. Are there any examples of numbers that are Martin-Löf random but computable?

  • 1
    $\begingroup$ No. For example, this follows from the fact that for a random number $0.x_1x_2\ldots$ the set of digits $j$ for which $x_j=a$ has a fixed value cannot contain an infinite recursively enumerable subset. $\endgroup$ – user138530 Mar 5 '15 at 1:34

Computability is a very strong way of not being random. One easy way to understand randomness is via betting strategies (i.e. constructive martingales). These work by starting with capital 1 (dollar, say) and allowing the player to bet any amount of his current capital on what the next bit of the sequence will be. If the sequence even has an infinite c.e. subset, then the player would be guaranteed to win at those bits, so his winnings would approach $\infty$.

I'll fill in details if you need.

| cite | improve this answer | |
  • $\begingroup$ Hey Quinn, How are you? $\endgroup$ – hot_queen Mar 8 '15 at 19:36
  • $\begingroup$ @hot_queen Fine-ish. I'm scheduled to finish in about a month. :| You? $\endgroup$ – Quinn Culver Mar 8 '15 at 23:59
  • $\begingroup$ Great, Where are you going next? I will be in Toronto starting this fall. Good luck with your defense etc. $\endgroup$ – hot_queen Mar 11 '15 at 14:21
  • $\begingroup$ I'm not sure. Probably Hawaii. Maybe hell. How's it been with Shelah? $\endgroup$ – Quinn Culver Mar 11 '15 at 14:22
  • $\begingroup$ I hope it's Hawaii. With Shelah, the hardest part is decoding what he writes. On most days I feel like a compiler checking his machine language proofs :( $\endgroup$ – hot_queen Mar 11 '15 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.