Thread for basic questions

For general discussion about Conway's Game of Life.
AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Thread for basic questions

Post by AforAmpere » February 28th, 2018, 2:51 pm

danny wrote:Are spaceships faster than c/3 really impossible in justfriends? Is there a proof?
On a similar vein, what B3 totalistic rules allow C/2? B3478/S15678 seems to only allow speeds up to C/3 orthogonal, but for some reason C/4 diagonal.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
cordership3
Posts: 129
Joined: August 23rd, 2016, 8:53 am
Location: Smome tomato
Contact:

Re: Thread for basic questions

Post by cordership3 » March 2nd, 2018, 12:02 pm

Would it be practical at all to make a version of apgsearch that works in a browser?
evil twin of cordership2

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Thread for basic questions

Post by Apple Bottom » March 2nd, 2018, 5:36 pm

cordership3 wrote:Would it be practical at all to make a version of apgsearch that works in a browser?
Not entirely impractical, I'd guess, as you could take the current C++ codebase, replace the assembly language bits with C++ code, and then compile the whole shebang for asm.js. (This obviously leaves out a lot of work that would have to be done, still.)

I think the bigger question is: whyever would you want to?
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Thread for basic questions

Post by Majestas32 » March 2nd, 2018, 6:20 pm

Make mobile apgsearch lol
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: Thread for basic questions

Post by dani » March 3rd, 2018, 11:45 pm

1. Could a puffer be made that is kind of like a moving otca metapixel?
1a. With/without leaving behind debris showing every generation

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: Thread for basic questions

Post by 77topaz » March 4th, 2018, 12:01 am

danny wrote:1. Could a puffer be made that is kind of like a moving otca metapixel?
1a. With/without leaving behind debris showing every generation
Hmm... Naszvadi's rule-110 guns in his Turing-completeness thread have a somewhat similar concept to that.

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » March 4th, 2018, 12:13 am

danny wrote:1. Could a puffer be made that is kind of like a moving otca metapixel?
1a. With/without leaving behind debris showing every generation
When Calcyman gets done compiling his replicator-megapixel, it will be trivial to program it to emulate various CA rules, so you can get all kinds of behavior along these lines.

That's going to be an impressively huge pattern, though. For something slightly more reasonable sized, maybe modify the self-synthesizing spaceship idea -- just knock out the self-destruct part, and it's certainly a puffer. It takes quite a bit more circuitry to leave a functioning metapixel behind at every cycle, but depending on how complicated a rule you're trying to emulate, it might not be too bad.

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: Thread for basic questions

Post by dani » March 4th, 2018, 12:32 am

dvgrn wrote:It takes quite a bit more circuitry to leave a functioning metapixel behind at every cycle, but depending on how complicated a rule you're trying to emulate, it might not be too bad.
I meant like a puffer that evolves a pattern specified by gliders or otherwise and puffs its evolution out onto the grid. So it would look like:

Code: Select all

x = 45, y = 4, rule = B3/S23
21bo9b2o$2o8b3o8b2o7b3o$b2o9bo7bo2bo6bo2bo6bobobo$bo9b2o8b2o8b2o!

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: Thread for basic questions

Post by 77topaz » March 4th, 2018, 2:16 am

danny wrote:
dvgrn wrote:It takes quite a bit more circuitry to leave a functioning metapixel behind at every cycle, but depending on how complicated a rule you're trying to emulate, it might not be too bad.
I meant like a puffer that evolves a pattern specified by gliders or otherwise and puffs its evolution out onto the grid. So it would look like:

Code: Select all

x = 45, y = 4, rule = B3/S23
21bo9b2o$2o8b3o8b2o7b3o$b2o9bo7bo2bo6bo2bo6bobobo$bo9b2o8b2o8b2o!
Hmm... I can imagine a metapixel-puffer doing that for a one-dimensional CA, but it would be rather more difficult for a two-dimensional one. You'd have to specify a fixed bounding box for the pattern for that to work, I think.

User avatar
cordership3
Posts: 129
Joined: August 23rd, 2016, 8:53 am
Location: Smome tomato
Contact:

Re: Thread for basic questions

Post by cordership3 » March 5th, 2018, 6:11 pm

Apple Bottom wrote:
cordership3 wrote:Would it be practical at all to make a version of apgsearch that works in a browser?
Not entirely impractical, I'd guess, as you could take the current C++ codebase, replace the assembly language bits with C++ code, and then compile the whole shebang for asm.js. (This obviously leaves out a lot of work that would have to be done, still.)

I think the bigger question is: whyever would you want to?
The thing is, I work on a lot of shared computers, where downloading cygwin and other programs to compile apgsearch would be inconvenient for others (or just hard to explain away). Since I can't use existing methods to run apgsearch, I thought of a browser-based apgsearch that could be run in a browser quickly. If this, for whatever reason, gets created, I hope the server doesn't get overrun by small hauls...

(also, would a .exe for apgsearch be at all practical?)
evil twin of cordership2

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Thread for basic questions

Post by Apple Bottom » March 6th, 2018, 6:47 am

cordership3 wrote:The thing is, I work on a lot of shared computers, where downloading cygwin and other programs to compile apgsearch would be inconvenient for others (or just hard to explain away).
Ah, fair enough.
(also, would a .exe for apgsearch be at all practical?)
This SHOULD be possible -- you can probably copy over the apgsearch executable from another computer, though if Cygwin's not installed you may have to link it statically, or else distribute whatever DLLs it depends on along with it.

Your mission, should you choose to accept it: investigate this, create a binary distribution of apgsearch that does not rely on Cygwin being installed, and build an MSI package for it. ;)
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » March 8th, 2018, 1:46 pm

Answering my own question from last December:
dvgrn wrote:How exactly are we supposed to use Rule 90 to reproduce all those other "RepetitionPeriods" from that mysterious Wolfram Cloud document? The "in-between" numbers not included in the A268754 sequence are even bigger and more outlandish, on average, than the A268754 values.
A little experimenting seems to indicate that the RepetitionPeriods are what you get if you run Rule 90 on a ring containing {WolframIndex} cells, starting with a single ON cell anywhere in the ring. (By "ring" I just mean the equivalent of a torus for 2D rules.)

I tried this using Golly's native Wolfram rule support -- e.g., W90:T96,0 for a period-32 repetition. Every number I tried checked out perfectly.

This method is definitely not recommended for longer periods, though. It seems that Golly's bounded-grid implementation slows things down more than usual for 1D rules. A custom rule table that simulates Rule 90 in place runs hundreds of times faster, and it's compatible with oscar.lua:

Code: Select all

@RULE Wolfram90
@RULE Wolfram90

@TABLE

n_states:2
neighborhood:oneDimensional
symmetries:reflect

1,1,1,0
1,1,0,1
1,0,0,0
0,1,1,0
0,1,0,1
0,0,0,0

Code: Select all

#C 1-tick predecessor of a period 87381 oscillator
x = 1, y = 1, rule = Wolfram90:T37,1
o!
Of course a compiled C executable would be several orders of magnitude faster again. Golly is still doing a silly amount of extra work not really needed for this specific case.

I'm very curious about what shortcuts might have been used to generate the numbers in the Wolfram Cloud document, to find out for example that the repetition period for WolframIndex 199 is 90546471444873528678335943241... especially given that many of the interesting cases (like the one above) don't return to their initial state, so you have to run for some number of ticks before starting to look for a repeat.

Code: Select all

#C apparently an oscillator or predecessor of an oscillator,
#C      with a 7-fold reduction in the default period:
#C  90546471444873528678335943241 = (2^99-1)/7, not
#C 633825300114114700748351602688 = (2^99-1)
x = 1, y = 1, rule = Wolfram90:P199,1
o!
You certainly couldn't apply the rule that many times and check for a repeated pattern, no matter how fast your computer might be, so it seems like it must be an impressively good shortcut.

EDIT: See the quote in this post for a workable approach.

EDIT 1/11/2019: I did some incomplete spot-checking of the Wolfram Cloud numbers a while back. There are other reductions by a factor of three in the Wolfram Cloud list, not previously mentioned anywhere that I've seen --

WolframIndex 101 -> 375299968947541 = (2^50-1)/3
WolframIndex 197 -> 105637550019019116791391933781 = (2^98-1)/3

And as stated elsewhere, WolframIndex 74 is wrong -- it should be twice the value of WolframIndex 37.

User avatar
muzik
Posts: 5614
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Thread for basic questions

Post by muzik » March 12th, 2018, 12:38 pm

How many (still lifes, oscillators, spaceships) with exactly 20 or under cells in their minimum phase have not yet come out of b3s23/C1?

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: Thread for basic questions

Post by 77topaz » March 12th, 2018, 3:19 pm

muzik wrote:How many (still lifes, oscillators, spaceships) with exactly 20 or under cells in their minimum phase have not yet come out of b3s23/C1?
It's going to be a pretty large number, considering that there are roughly 90'000 exactly-20-bit still lifes alone that haven't yet appeared on Catagolue in b3s23/C1.

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » March 12th, 2018, 3:20 pm

muzik wrote:How many (still lifes, oscillators, spaceships) with exactly 20 or under cells in their minimum phase have not yet come out of b3s23/C1?
Way-too-many (for still lifes), plus somewhere around 5000 (for oscillators), plus one (if you count the 18-bit pseudo-spaceship LWSS on LWSS, which I suspect-but-don't-know-for-sure is separated by apgsearch so it's probably occurred but we haven't noticed it), plus the loafer. Plus any other tiny spaceships that we haven't discovered.

All of which adds up to precisely way-too-many -- well over a hundred thousand. As of just now Catagolue only has 12,863 of the 112,243 20-bit still lifes, and only 10,352 of the 45,759 19-bit still lifes, and so on down to where darn it all we're still missing one of the 619 14-bitters.

My sources of information are Catagolue's statistics page and Mark Niemiec's spaceships page. The 5000 figure for oscillators comes from Mark's oscillators page, but I'm not quite clear on whether any more 20-bit or smaller oscillators might still show up the way the 21-bit Runny Nose did.

User avatar
muzik
Posts: 5614
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Thread for basic questions

Post by muzik » March 13th, 2018, 9:44 am

Let's see... 1+61+597+3053+11480+35411+99385 comes out to 149988 still lifes, 149989 objects including the loafer, and roughly 154989 including the about 5000 oscillators. Can someone get a Dyson sphere or something over here already?

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » March 13th, 2018, 12:02 pm

muzik wrote:Let's see... 1+61+597+3053+11480+35411+99385 comes out to 149988 still lifes, 149989 objects including the loafer, and roughly 154989 including the about 5000 oscillators. Can someone get a Dyson sphere or something over here already?
We don't need a Dyson sphere, we just need a less ambitious threshold! Just pick 14 instead of 20 and we have a chance of finding everything.

Conversely, pick 40 instead of 20 and even a Dyson sphere might not be enough, since a Dyson sphere only gives us a factor of 10^20 or 10^25 or so improvement over the current status quo. I guess you could add another 10^10 or 10^20 improvement if you want to assume we'll figure out how to make computers that much faster and more efficient, by the time we've finished building the Dyson sphere.

I think that still doesn't get us to 10^77, the size of 16x16-soup space. If we run the Dyson sphere for enough years, we might manage to get there before the Sun burns out, but it might be a close call.

Anyway, somewhere up there Catagolue's methodology will become kind of questionable, since we already know there are 16x16 soups containing loafers and every other spaceship, oscillator or still life with a 16x16 or smaller bounding box. But somehow we're not really as interested if the object is already there at T=0. Might as well just enumerate all the 16x16 patterns instead of picking them randomly -- would save a lot of time if we're going to end up trying them all anyway.

There's a simpler reason why a Dyson sphere might not be sufficient for a 40-bit threshold. Never mind Sir Robin-sized things, possibly some spaceships with 40 bits or less don't have a 16x16 predecessor, in which case no matter how long we run apgsearch they'll never show up. Some known 40-bit spaceships are 13x25, for example, so at least there definitely isn't a soup where they appear before T=5.

-- Yes, it's a strange thought experiment where we convert the entire solar system into computronium but never think of bumping up Catagolue's soup size at least to 32x32.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Post by Macbi » March 13th, 2018, 12:44 pm

I don't think even Dyson Sphere + quantum computers would let us run every 16*16 soup. There are 2^256 soups, but Grover's algorithm will give a quadratic speedup so we "only" have to run 2^128 of them. The power output of the sun is about 2^75 times what my computer requires, and my computer does 2^11 soups per second, so we would need about 2^(128 - 11 - 75) seconds, which is 140000 years.

That's assuming my computer does as many operations-per-second as a quantum computer in the far future, which is unrealistic (although I couldn't tell you in which direction it was unrealistic).

On the other hand, once you have the technology to build one Dyson sphere it isn't actually much harder to build 140000 of them, so it's not impossible we will have the answer one day.

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » March 13th, 2018, 1:58 pm

Macbi wrote:The power output of the sun is about 2^75 times what my computer requires, and my computer does 2^11 soups per second, so we would need about 2^(128 - 11 - 75) seconds, which is 140000 years.
Oh, good, then my math isn't too far off. I did say
dvgrn wrote:If we run the Dyson sphere for enough years, we might manage to get there before the Sun burns out...
However, I didn't even try to sort out the probability power laws. I guess we're guaranteed to find most of the 20-bit still lifes and oscillators, though there are a few that don't fit in 16x16. 20-bit barber poles and ludicrous-squaredly long canoe (or whatever you call that) are 17x17, so it's not an absolutely foregone conclusion that 16x16 soups even exist that produce these. Grover's algorithm can't find soups that don't exist.

And that doesn't even count the famous Pi-R-Squared spaceship*, where two pi grandparents and two R-pentominos, totaling 20 bits in a 55x34 bounding box, happen to interact in just the right way to reproduce a copy of themselves offset by one cell every 137 ticks. That might also have a 16x16 predecessor, but it's also not a foregone conclusion.

* seen briefly in 1974 on a PDP-12 display by Tony Honcho Jarnow, produced from a 128x80 random soup, just before an unfortunate power outage due to tripping on a power cable.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Thread for basic questions

Post by calcyman » March 13th, 2018, 2:51 pm

Wait, isn't Grover's algorithm very much non-parallelisable? As I understand it, don't you have to perform the Grover rotation gate O(2^128) times in succession and then make a measurement?
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Post by Macbi » March 13th, 2018, 3:54 pm

calcyman wrote:Wait, isn't Grover's algorithm very much non-parallelisable? As I understand it, don't you have to perform the Grover rotation gate O(2^128) times in succession and then make a measurement?
Hmmm... you could be right. We would need an extension of Grover's algorithm anyway, since we're not searching only one thing, and we also want to tally up object counts (essentially a quantum counting algorithm). Since Grover's algorithm is probabilistic it requires repeats to find the answer with certainty, and these repeats could definitely be done in parallel (which it what I was thinking earlier). But each repeat still needs to do O(N^1/2) operations, and it doesn't immediately seem like these can be done in parallel. So it looks like you're right. :oops:

In fact it looks like no quantum search algorithm can be parallelised (https://arxiv.org/pdf/quant-ph/9711070.pdf). :(

EDIT: It's probably still good for each individual computer to be using Grover's algorithm. We can give them each a portion of the search space. So not being parallelisable doesn't hurt us by O(number of computers), but only by O(sqrt(number of computers)). Which is still terrible.

EDIT2: Also, the catagolue currently uses 10^-9 of the world's energy, and there are only 10^11 stars in the Milky Way, so we might only have about 100 to play with. :D

Hooloovoo
Posts: 38
Joined: July 11th, 2015, 8:59 pm

Re: Thread for basic questions

Post by Hooloovoo » March 14th, 2018, 1:32 am

dvgrn wrote:And that doesn't even count the famous Pi-R-Squared spaceship*, where two pi grandparents and two R-pentominos, totaling 20 bits in a 55x34 bounding box, happen to interact in just the right way to reproduce a copy of themselves offset by one cell every 137 ticks. That might also have a 16x16 predecessor, but it's also not a foregone conclusion.

* seen briefly in 1974 on a PDP-12 display by Tony Honcho Jarnow, produced from a 128x80 random soup, just before an unfortunate power outage due to tripping on a power cable.
Where can I read more about this? My google-fu has failed me.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Thread for basic questions

Post by wildmyron » March 14th, 2018, 2:17 am

Hooloovoo wrote:
dvgrn wrote:And that doesn't even count the famous Pi-R-Squared spaceship*, where two pi grandparents and two R-pentominos, totaling 20 bits in a 55x34 bounding box, happen to interact in just the right way to reproduce a copy of themselves offset by one cell every 137 ticks. That might also have a 16x16 predecessor, but it's also not a foregone conclusion.

* seen briefly in 1974 on a PDP-12 display by Tony Honcho Jarnow, produced from a 128x80 random soup, just before an unfortunate power outage due to tripping on a power cable.
Where can I read more about this? My google-fu has failed me.
dvgrn is pulling your leg :D Tony Honcho Jarnow is an anagram of John Horton Conway.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

Hooloovoo
Posts: 38
Joined: July 11th, 2015, 8:59 pm

Re: Thread for basic questions

Post by Hooloovoo » March 14th, 2018, 2:41 am

I just got on to edit my post to ask if if I was being messed with :P

I definitely didn't notice the anagram, though, nice job!

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Thread for basic questions

Post by Macbi » March 14th, 2018, 3:35 am

You can tell when dvgrn is messing with you because he uses the number 137.

Post Reply