Saka wrote: 83bismuth38 wrote:
If your familiar with winlifesearch, I set it to a 20x20 grid and set the oscillator period to 19. approx 2 billion calculations so far and from what I can tell, it's nowhere close yet. wish me luck, at this rate, it will last a good day or so.
I doubt it will only take a day. I spent a week or so just trying to find this 2c/5 spaceship with normal WLS...
Well, 33x19 divided by two (due to the symmetry) is almost as big as 20x20 -- but 2c/5 is period 5, so the period 19 search really has to look through four times as many unknown bits.
That doesn't mean that the 20x20 search will take just four times as long, though -- as you add more unknown cells, searches take exponentially
longer. Unless you get really incredibly lucky, this search will still be going in a trillion trillion trillion years (assuming you have AC power for that long).
Let's say for every two unknown cells you add, the search takes twice as long. I don't know if that's anywhere near right, it depends on the rule and on the search algorithm to some extent, but it's something like that -- a good enough guess for this purpose, as you'll see. The general idea is, WLS has to try pretty much the whole previous search twice, once with the first new unknown cell ON and once with it OFF -- and maybe the other unknown cell is forced either ON or OFF by the search conditions.
-- Okay, so 33x19x5 generations divided by two is a bit over 1500 unknown cells. By Saka's testimony, it takes more than a week to search that. Let's be really optimistic and say that's a ten-day search.
This 20x20x19 search is 7600 unknown cells -- about five times as many. But the five-times statistic doesn't even matter! What matters is that it's about 7600 - 1500 = about 6000 cells more.
The guess above was that for every two cells you add, the total search time doubles. Three thousand doublings, 2^3000, times ten days, is... kind of a big number. I think it's 904 digits long, or say an even 900 digits if you count in centuries. That's so big that a trillion trillion trillion doesn't even begin to describe it.
So it doesn't really matter if the search time only doubles with every three cells you add, or every ten -- you still have way too many unknown cells in that search. You'd only get a result if period-19 oscillators are really really common, so that WLS runs into one pretty much everywhere it looks -- and we kind of know from Catagolue
soup searches that that isn't the case.