Math Genome Fun 2, UPB and beyond?

This is a follow-on from the original “Math Genome Fun” thread here

I think it’s time to test out GAs on a bigger problem, the old one was at the boundary of home computation for an exhaustive search (OMD I said “search!” get on that Mung) – but I’m going to propose a *much* bigger search / smaller target.

Friends, you target is Pi

I’ve chosen Pi because of its qualities, being irrational and transcendental you cannot describe it in an equation, only approximate it.

Our target is the first 150 digits of Pi.

Our vocabulary is the same numbers and operators as before: [1,2,3,4,5,6,7,8,9,+,-,*,/], but this time they can all be used as often as required and the genome can be anywhere from 1 to 1000 characters in length.

The design approximation is now harder due to the decimal place and the absence of zeros in our vocabulary (but there’s quite a few in Pi).

I’ve done no computation on this myself, can a GA find that proverbial needle in a haystack?

 

0

131 thoughts on “Math Genome Fun 2, UPB and beyond?

  1. Before I tackle Rich’s problem, I thought it would be interesting to go after a related problem, which is:

    How closely can we approximate pi using the rules of the previous thread — i.e., by forming an expression that uses each digit from 1-9, and each of the four operators +-*/, exactly once?

    In nine out of ten trials, the GA took less than five minutes to find a solution within .0000003 of pi (the tenth trial took five minutes and seven seconds). Here they are, sorted by execution time:

    5:07
    4:05
    3:40
    3:39
    2:56
    1:58
    0:23
    0:22
    0:11
    0:00.38 (!)

    The two solutions were 8-3+245*6/791 and 4+9*312/678-5, which, believe it or not, are exactly equal.

    They evaluate to 3.1415929 vs. pi at 3.1415927 (rounded), for an error of less than 0.0000003 .

    I haven’t done an exhaustive search, but I did let the GA run for about five hours this afternoon. It didn’t find anything better than the two solutions listed above.

    0
  2. I tried the GA on a handful of different constants, giving it five minutes to work on each one. The results are listed below in the following format:

    constant
    expression
    error

    Results:

    pi
    9*312/678+4-5
    0.00000027

    e
    4-726/859*3+1
    0.00000476

    my birthday, in .mmddyyyy format
    <redacted>
    0.00000068

    0.1010010001
    6+218*3/594-7
    0.00000910

    1.23456789
    5-4*186/972+3
    0.00000001
    .

    0
  3. My mistake, DiEb.

    I was prioritizing addition over subtraction instead of parsing them left to right.

    I’ll fix my code and rerun — tomorrow.

    Meanwhile, my second result for pi — 9*312/678+4-5 — still works, as do the expressions for the other constants except for e.

    0
  4. keiths: for an error of less than 0.0000003 .

    a infinitesimal error is still an error

    petrushka: Makes one wonder if there’s such a thing as a non-computable string.

    As long as there is an error between the model and the actual constant I would say that non-computable is a safe bet .

    Richardthughes: Might have some relevance to FMM’s claims

    might very well

    I’ll check it out, Thanks

    peace

    0
  5. fifth,

    As long as there is an error between the model and the actual constant I would say that non-computable is a safe bet .

    That’s because you still don’t understand computability after all these months of discussion.

    It’s a trivial exercise to demonstrate the existence of computable numbers whose value cannot be exactly matched by a expression constructed from the characters in [1,2,3,4,5,6,7,8,9,+,-,*,/], each used exactly once.

    0
  6. My brute force algo found this in 2 1/2 minutes (8 threads @ 4.8GHz):

    That’s on Windows. Running in windows it crunches expressions at half the rate of Linux because the -Qnew switch doesn’t work on threads, don’t know why, so I need to transform each expression to append ‘.0’ to digits so that it evaluates divisions with decimals

    Best = [‘16.0/113.0+3.0’]
    Current PI = 3.14159292035 found at: 00:02:29
    Mininum difference = 2.66764189405e-07
    Total Iterations = 48512859 – 2.25905603834 %
    Valid Expressions = 18914473
    Iterations/s ( /core ) = 292772.405934 ( 36596.5507417 )
    Avg. Iterations/s ( /core ) = 323395.344518 ( 40424.4180648 )

    Time elapsed = 00:02:30

    0
  7. On Linux:

    Best = [’16/113+3′]
    Current PI = 3.14159292035 found at: 00:01:05
    Mininum difference = 2.66764189405e-07
    Total Iterations = 115224568 – 1.24926726949e-09 %
    Valid Expressions = 49606038
    Iterations/s ( /core ) = 623945.540505 ( 89135.077215 )
    Avg. Iterations/s ( /core ) = 677452.730241 ( 96778.9614629 )

    Time elapsed = 00:02:50

    And…

    Best = [‘3+32/226’, ‘3+48/339′, ’16/113+3’, ‘3+96/678’]
    Current PI = 3.14159292035 found at: 00:02:56
    Mininum difference = 2.66764189405e-07
    Total Iterations = 121577256 – 1.3181432508e-09 %
    Valid Expressions = 52416654
    Iterations/s ( /core ) = 635266.073734 ( 90752.2962477 )
    Avg. Iterations/s ( /core ) = 675110.124224 ( 96444.3034606 )

    Time elapsed = 00:03:00

    0
  8. keiths: That’s because you still don’t understand computability after all these months of discussion.

    au contraire I think it us you who is missing the point here.

    I know this because you thought lossless information integration was about our ability to recall memories rather than about data compression

    keiths: It’s a trivial exercise to demonstrate the existence of computable numbers whose value cannot be exactly matched by a expression constructed from the characters in [1,2,3,4,5,6,7,8,9,+,-,*,/], each used exactly once.

    Yes,

    those rules are not binding in this exercise though

    and if we “know” numbers that can’t be matched by an expression then the function by which we came to know those numbers is noncomputable

    once again recall the definition of an integrating function

    quote;
    the knowledge of m(z)does not help to describe m(z′),when z and z′are close.
    end quote:

    sound familiar?

    peace

    0
  9. keiths:

    It’s a trivial exercise to demonstrate the existence of computable numbers whose value cannot be exactly matched by a expression constructed from the characters in [1,2,3,4,5,6,7,8,9,+,-,*,/], each used exactly once.

    fifth:

    those rules are not binding in this exercise though

    They were binding in the exercise I was conducting and upon which you were commenting.

    Besides, it’s also true of the problem Rich is posing here. There are zillions of computable numbers whose values cannot be exactly matched by an expression constructed according to the rules of this thread, which limit you to 1,000 characters or less selected from [1,2,3,4,5,6,7,8,9,+,-,*,/].

    0
  10. fifth,

    It astounds me that after all these months, you still don’t understand that pi and e are computable numbers.

    It’s even there in the Wikipedia article on computable numbers:

    The computable numbers include many of the specific real numbers which appear in practice, including all real algebraic numbers, as well as e, pi, and many other transcendental numbers.

    I’m not used to this kind of lack of curiosity. Don’t you care about this stuff? At all?

    0
  11. keiths: It astounds me that after all these months, you still don’t understand that pi and e are computable numbers.

    you are——still—–confounding the concepts of computable number and computable function.

    Any finite number can be produced by an algroythym. any infinite number can be algorithmically approximated to any arbitrary level of precision you desire

    the noncomputable part is the part where you choose which algroythym to use and what level of precision is sufficient .

    Computers don’t choose.

    peace

    0
  12. fifth,

    you are——still—–confounding the concepts of computable number and computable function.

    The confusion is yours.

    petrushka wrote

    Makes one wonder if there’s such a thing as a non-computable string.

    You responded:

    As long as there is an error between the model and the actual constant I would say that non-computable is a safe bet .

    It’s the same mistake you’ve been making for months. From May 2015:

    Lets take the Pi for example.
    If we were to represent Pi numerically we would have a irrational constant. In other words Pi is non-computable in the sense that we are using the term here

    This is intuitively obvious given that the information in the concept PI is fully integrated. So the K complexity necessary to reproduce PI entirely would be effectively infinite, Again that is just another way of saying that PI is non-computable.

    Your error was pointed out then, and it’s being pointed out now. Will you be making the same mistake six months from now? You could crack a book or two, but you seem to have no genuine interest in this stuff.

    Whence this lack of curiosity?

    0
  13. Part of the problem is embedded in the game.

    Any substring of pi is computable in the hard sense of the word. That is, it can be computed in fact, not just in theory.

    In fact, there are algorithms for computing pi starting at any arbitrary digit, without having to compute the intervening digits.

    So I continue to ask Fifth, how do we verify or validate his game.

    I don’t think majority rules in mathematics.

    0
  14. fifthmonarchyman: the noncomputable part is the part where you choose which algroythym to use and what level of precision is sufficient .

    Computers don’t choose.

    Why are you using “computable/non-computable” for something that computers don’t do? Maybe you should invent more suitable terminology.

    0
  15. Neil Rickert: Why are you using “computable/non-computable” for something that computers don’t do? Maybe you should invent more suitable terminology.

    I’m using the terminology in the way that Phil Maguire does. There is no need to reinvent the wheel.

    The problem is not in the terminology computers compute by definition
    You call something that computers are unable to do a noncomputable function.

    peace

    0
  16. petrushka: Any substring of pi is computable in the hard sense of the word. That is, it can be computed in fact, not just in theory.

    What is not computable is the decision to halt the algorithm at a certain point

    petrushka: In fact, there are algorithms for computing pi starting at any arbitrary digit, without having to compute the intervening digits.

    What they don’t do, indeed can’t do is decide which digit to stop at

    peace

    0
  17. fifthmonarchyman: You call something that computers are unable to do a noncomputable function.

    But that does not make any sense.

    Computers are not able to form raindrops or ice crystals. Yet those are completely natural phenomena. Calling them “non-computable” is just a way of confusing people.

    0
  18. Neil Rickert,

    Computers are not able to form raindrops or ice crystals. Yet those are completely natural phenomena.

    There is no evidence that humans are anything other than completely natural phenomena either, which would seem to undermine fifthmonarchyman’s position.

    0
  19. fifth,

    What is not computable is the decision to halt the algorithm at a certain point

    More goalpost-moving. Have you no shame, fifth?

    If it were about deciding when to halt, then even 1/3 would be “non-computable”. Which digit do you stop at?

    Isn’t it time to acknowledge that you got computability and Kolmogorov complexity completely wrong?

    This is eyeroll material:

    Lets take the Pi for example.
    If we were to represent Pi numerically we would have a irrational constant. In other words Pi is non-computable in the sense that we are using the term here

    This is intuitively obvious given that the information in the concept PI is fully integrated. So the K complexity necessary to reproduce PI entirely would be effectively infinite, Again that is just another way of saying that PI is non-computable.

    If you were serious about doing science, you would acknowledge your mistakes and learn from them.

    0
  20. keiths: More goalpost-moving. Have you no shame, fifth?

    It’s not about moving the goalposts It’s about informing you yet again tor the hundredth time where the goalposts have always been.

    Perhaps this time you finally understand.

    peace

    0
  21. Neil Rickert: Computers are not able to form raindrops or ice crystals. Yet those are completely natural phenomena. Calling them “non-computable” is just a way of confusing people.

    Human cognition is natural as well and it’s non-computable,
    It’s not confusing at all unless you are a certain kind of materialist.

    peace

    0
  22. fifth,

    What is not computable is the decision to halt the algorithm at a certain point

    keiths:

    More goalpost-moving. Have you no shame, fifth?

    If it were about deciding when to halt, then even 1/3 would be “non-computable” [by your criterion]. Which digit do you stop at?

    fifth:

    It’s not about moving the goalposts It’s about informing you yet again tor the hundredth time where the goalposts have always been.

    You’re as excruciatingly bad at bluffing as you are at math and computer science.

    You claimed that pi is non-computable because it has infinite Kolmogorov complexity. To anyone who understands those concepts, your claim is laughable.

    Do you want to double down? Do you still believe the following?

    So the K complexity necessary to reproduce PI entirely would be effectively infinite, Again that is just another way of saying that PI is non-computable.

    Do you still believe that, or do you acknowledge your (egregious) mistake?

    In your world, does 1/3 have infinite Kolmogorov complexity, just like pi? Is 1/3 non-computable?

    0
  23. fifthmonarchyman: It’s not about moving the goalposts It’s about informing you yet again tor the hundredth time where the goalposts have always been.

    That might be true. But only because it has always been nonsensical.

    0
  24. fifthmonarchyman: Human cognition is natural as well and it’s non-computable,
    It’s not confusing at all unless you are a certain kind of materialist

    Not sure about materialism but the belief that a deity knows in advance the results of cognition seems to refute the non computability of human cognition

    0
  25. keiths: Whence this lack of curiosity?

    Now that is hilarious!

    Everyone here is a know-it-call and fifth continually asks them how they know things. And now he’s accused of a lack of curiosity. Talk about Alice in Wonderland.

    0
  26. keiths: In your world, does 1/3 have infinite Kolmogorov complexity, just like pi? Is 1/3 non-computable?

    in the context of the game .333333333 is indistinguishable from .33333333

    So the string that represents 1/3 is not the result of a noncomputable function

    Neil Rickert: That might be true. But only because it has always been nonsensical.

    Did you read the paper?

    newton: the belief that a deity knows in advance the results of cognition seems to refute the non computability of human cognition

    How so?

    peace

    0
  27. Neil Rickert: fifthmonarchyman: Human cognition is natural as well and it’s non-computable

    You cannot prove that. You cannot even define what that means.

    Did you read the paper?

    peace

    0
  28. A great deal of needless back ad forth might be avoided if you would simply document your decision making procedure. You could, for example, take the data I submitted and tell us what you find in it. Preferably with soma annotated graphs.

    I’ve spent a fair amount of time running the program and have no idea what you are seeing. All the graphs have Ws. I need to see the whole graph with some annotation.

    0
  29. fifth,

    Refusing to acknowledge your mistakes just makes you look ridiculous, particularly when they are whoppers like this one.

    You wrote:

    Lets take the Pi for example.
    If we were to represent Pi numerically we would have a irrational constant. In other words Pi is non-computable in the sense that we are using the term here

    This is intuitively obvious given that the information in the concept PI is fully integrated. So the K complexity necessary to reproduce PI entirely would be effectively infinite, Again that is just another way of saying that PI is non-computable.

    As I said:

    To anyone who understands those concepts, your claim is laughable.

    Instead of admitting your mistakes, you shamelessly tried to shift the goalposts:

    What is not computable is the decision to halt the algorithm at a certain point

    If that were true of pi, it would also be true of 1/3. Your evasions are backfiring on you, and you don’t even understand the concepts on which your argument is supposedly based.

    0

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.