1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complexity of irrationals

  1. Aug 1, 2013 #1
    How would I figure out the Kolmogorov complexity of an irrational number?
    Could I just look at the shortest formula to compute that number.
    If it is an uncomputable real, does it have infinite complexity?
  2. jcsd
  3. Aug 1, 2013 #2
    Yes, and yes.
  4. Aug 1, 2013 #3
    I saw an interesting example online the other day. Take a noncomputable number and interperse 0's in every other digit position. Then for each finite-length initial segment, it takes just a little more than half as much information to compute the number with the 0's in every other position as it does to compute the original number. So not all noncomputable numbers are equally random. It's tricker than I'd realized.
    Last edited: Aug 1, 2013
  5. Aug 3, 2013 #4
    where did you see this example
  6. Aug 5, 2013 #5


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That sounds suspiciously like infinity/2 = infinity.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook