You can subscribe to this list here.
2005 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
(15) |
Aug
|
Sep
(72) |
Oct
(34) |
Nov
(10) |
Dec
(20) |
---|---|---|---|---|---|---|---|---|---|---|---|---|
2006 |
Jan
|
Feb
(22) |
Mar
(9) |
Apr
(11) |
May
(18) |
Jun
(68) |
Jul
(10) |
Aug
(4) |
Sep
(13) |
Oct
(29) |
Nov
(21) |
Dec
(24) |
2007 |
Jan
(32) |
Feb
(19) |
Mar
(11) |
Apr
(14) |
May
(8) |
Jun
(7) |
Jul
(3) |
Aug
|
Sep
|
Oct
(8) |
Nov
(26) |
Dec
(16) |
2008 |
Jan
(1) |
Feb
(4) |
Mar
(4) |
Apr
(25) |
May
(23) |
Jun
(22) |
Jul
(18) |
Aug
(61) |
Sep
(129) |
Oct
(106) |
Nov
(99) |
Dec
(24) |
2009 |
Jan
(6) |
Feb
(2) |
Mar
(29) |
Apr
(84) |
May
(106) |
Jun
(70) |
Jul
(56) |
Aug
(42) |
Sep
(62) |
Oct
(140) |
Nov
(38) |
Dec
(9) |
2010 |
Jan
(19) |
Feb
(15) |
Mar
(32) |
Apr
(36) |
May
(28) |
Jun
(17) |
Jul
(12) |
Aug
(13) |
Sep
(7) |
Oct
(9) |
Nov
(156) |
Dec
(56) |
2011 |
Jan
(53) |
Feb
(25) |
Mar
(6) |
Apr
|
May
(1) |
Jun
(22) |
Jul
(8) |
Aug
(20) |
Sep
(50) |
Oct
(60) |
Nov
(44) |
Dec
(3) |
2012 |
Jan
(2) |
Feb
(11) |
Mar
(32) |
Apr
(35) |
May
(13) |
Jun
(90) |
Jul
(15) |
Aug
(27) |
Sep
(15) |
Oct
(28) |
Nov
|
Dec
|
2013 |
Jan
|
Feb
(119) |
Mar
(91) |
Apr
(68) |
May
(29) |
Jun
(24) |
Jul
(4) |
Aug
(14) |
Sep
(3) |
Oct
(11) |
Nov
(31) |
Dec
(36) |
2014 |
Jan
(48) |
Feb
(1) |
Mar
(23) |
Apr
(14) |
May
(15) |
Jun
(4) |
Jul
(8) |
Aug
(18) |
Sep
|
Oct
(14) |
Nov
|
Dec
(5) |
2015 |
Jan
(2) |
Feb
|
Mar
(11) |
Apr
(3) |
May
(44) |
Jun
(14) |
Jul
(7) |
Aug
(2) |
Sep
(5) |
Oct
(23) |
Nov
(27) |
Dec
(7) |
2016 |
Jan
(15) |
Feb
(22) |
Mar
(23) |
Apr
(41) |
May
(25) |
Jun
(1) |
Jul
(27) |
Aug
(9) |
Sep
(5) |
Oct
|
Nov
(27) |
Dec
|
2017 |
Jan
|
Feb
|
Mar
(3) |
Apr
(2) |
May
(1) |
Jun
(18) |
Jul
(16) |
Aug
(11) |
Sep
|
Oct
(3) |
Nov
|
Dec
|
2018 |
Jan
(11) |
Feb
(2) |
Mar
(3) |
Apr
|
May
(13) |
Jun
(12) |
Jul
(16) |
Aug
|
Sep
|
Oct
(1) |
Nov
|
Dec
|
2019 |
Jan
|
Feb
(3) |
Mar
(21) |
Apr
(8) |
May
(12) |
Jun
|
Jul
|
Aug
(4) |
Sep
(4) |
Oct
(2) |
Nov
(5) |
Dec
(16) |
2020 |
Jan
|
Feb
|
Mar
(1) |
Apr
(2) |
May
(16) |
Jun
|
Jul
(10) |
Aug
(24) |
Sep
(31) |
Oct
(17) |
Nov
(4) |
Dec
|
2021 |
Jan
(3) |
Feb
|
Mar
|
Apr
(1) |
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
(4) |
Nov
(12) |
Dec
(10) |
2022 |
Jan
|
Feb
(3) |
Mar
(2) |
Apr
(15) |
May
(4) |
Jun
|
Jul
|
Aug
(15) |
Sep
|
Oct
|
Nov
|
Dec
|
2023 |
Jan
|
Feb
|
Mar
|
Apr
(3) |
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
2024 |
Jan
|
Feb
|
Mar
(1) |
Apr
(6) |
May
(1) |
Jun
|
Jul
(1) |
Aug
(3) |
Sep
|
Oct
|
Nov
|
Dec
(1) |
2025 |
Jan
(1) |
Feb
|
Mar
(1) |
Apr
|
May
|
Jun
(1) |
Jul
(3) |
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
S | M | T | W | T | F | S |
---|---|---|---|---|---|---|
|
|
|
|
|
1
|
2
|
3
|
4
(1) |
5
(1) |
6
|
7
(3) |
8
(5) |
9
(1) |
10
(1) |
11
(1) |
12
(1) |
13
(17) |
14
(23) |
15
(16) |
16
(4) |
17
(8) |
18
(6) |
19
(4) |
20
(3) |
21
(2) |
22
(12) |
23
(3) |
24
(4) |
25
(2) |
26
|
27
|
28
(1) |
|
|
From: Dean H. <dea...@ya...> - 2013-02-28 19:51:49
|
If I've computed correctly, this Turmite becomes a period 6 oscillator in generation 4^967 + 7*2^967 + 1423305639 ~ 1.556 * 10^582; its final population is 2^967 + 66416: {{{1,2,1},{2,4,1},{1,1,0}}, {{0,2,2},{1,1,1},{2,1,1}}, {{2,4,3},{1,2,2},{2,1,2}}, {{0,8,0},{1,8,3},{2,1,3}}} Here's how I compute that, in case anyone wants to check: I run the pattern in Golly to gen 68093080. From then until gen 4^967 + 7*2^967 + 68092096, the Turmite is doing a binary count in a vertical line, while extending a horizontal line 1 unit to the left each time it increments the counter. Specifically, for n from 1 to 967, in gen g(n) = 4^n + 7*2^n - n + 68093063 the Turmite is n units above the bottom of the pattern, pointed upward in a cell in state 2; the rest of the vertical line has cells in state 1, except for the topmost cell. The population in gen g(n) is 2^n + 9224. I run the pattern to gen g(10) = 69148797, in order to create part of the horizontal line at the bottom left. Then I move the Turmite to the position 967 units above the bottom and set the generation to g(967). At this point the pattern is correct except for the length of the horizontal line at the bottom left, which should be 2^967 - 2^10 units longer. I let the pattern run 1355213543 more gens, at which point it enters a p6 cycle. During this time, it never visits the area of the long horizontal line, so the fact that the line is too short doesn't affect where the Turmite goes. The final population of the modified pattern is 67440; adding 2^967 - 2^10 to that gives the population that I mentioned above. I've tried a bunch of similar 4-state, 3-color rules, in which a binary counter controls a growing line, and this is the longest-lived one that I've been able to track to completion. Some finish more quickly, and some obviously run forever, but there are many that I couldn't track, so it's unlikely that this one is the best of the bunch. There could easily be some whose times to finish involve a tower of exponentials like 2^(2^1000) or more. Here are a few others of this type that I find interesting: Draws 4 exponential graphs: {{{2,4,3},{2,4,1},{1,1,0}}, {{0,8,2},{1,1,1},{2,1,1}}, {{1,4,3},{1,1,2},{2,2,2}}, {{0,2,0},{1,1,3},{2,8,3}}} Not exactly a fractal, but almost: {{{0,2,3},{1,1,0},{2,2,2}}, {{1,4,0},{1,1,1},{2,2,1}}, {{0,8,1},{1,1,2},{2,1,2}}, {{2,2,0},{2,4,2},{1,1,3}}} Grows mostly horizontally; I don't know if it becomes predictable: {{{1,2,3},{2,4,1},{1,1,0}}, {{0,8,2},{1,1,1},{2,1,1}}, {{1,4,3},{1,1,2},{2,2,2}}, {{0,2,0},{1,1,3},{2,2,2}}} Does this ever finish?: {{{2,2,3},{2,4,1},{1,1,0}}, {{0,8,2},{1,1,1},{2,1,1}}, {{1,4,3},{1,1,2},{2,2,2}}, {{0,2,0},{1,1,3},{2,8,3}}} Dean Hickerson |
From: Robert M. <mr...@gm...> - 2013-02-25 03:58:57
|
Hi Joel, On Sun, Feb 24, 2013 at 9:01 PM, Joel Snyder <joe...@gm...>wrote: > Sorry, I didn't mean to misrepresent myself as affiliated with GT by > citing the great solid curves they host. I've been working on this > project by myself in my spare time, unaffiliated with other > organizations in regards to this project. > Okay, no problem! It's still a great project. Your first email was pretty terse on details of all kinds, so I had to guess (-: However, I later discovered a greedy TSP algorithm that also starts > from a convex hull. It adds into the hull connections to a vertex with > least distance from the hull one at a time, until all vertices lie on > a complex, concave hull. > Yes, convex hulls of a sort seem to be a good way to make TSP paths. Like I said before, I think your approach looks pretty good. Thanks for the valuable tips. Honestly, I hadn't thought about running > _actual_ multiple instances of Golly. > > Originally, I was hoping to just import Python's multiprocessing > module and Pool map over the inner search loop, splitting up the rule > space evenly across processes. This loop just reopens the file, runs > some rules, and returns. However, I think I missed comprehension of Python's (or Golly's) ability for multiprocessing. Is Pool an option > when running inside a Golly script, or do I need real instances of > Golly somehow like Robert suggested : bgollys with shell, or Gollys > each with their own copy of the script? > There is no intrinsic multitasking ability in Golly. I doubt that the Process or Pool methods would work at all. If they do work, then each of your processes/threads would be competing with one another to control a single Golly pattern. I did try a simple Golly python script to spawn two threads using Process, and have them so time.sleep() and print stuff using g.show(), but it gives a strange error ending with "StderrCatcher instance has no attribute 'flush'. If you want to use multiple CPU cores, you will definitely need to launch multiple Golly processes to do it. But you have a choice of either making the Python script be the master, or having each Golly running a separate Python script. -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com |
From: Joel S. <joe...@gm...> - 2013-02-25 02:01:47
|
On Sun, Feb 24, 2013 at 9:25 AM, Robert Munafo <mr...@gm...> wrote: > I see that this is a very involved project that you (and others at GT?) have > been working on for a long time. Sorry, I didn't mean to misrepresent myself as affiliated with GT by citing the great solid curves they host. I've been working on this project by myself in my spare time, unaffiliated with other organizations in regards to this project. > It would help to have more of an introduction. Are there any papers on this > approach? Upon what theory is it known that any type of physical simulation > at all (like wave fronts, soap-bubbles, etc.) can produce candidate TSP > paths? As for a foundation theory, to this point it mainly rests on a personal conjecture. Originally it began as my own intuitive heuristic when looking for a good solution manually, and seemed to match well with known optimal solutions. However, I later discovered a greedy TSP algorithm that also starts from a convex hull. It adds into the hull connections to a vertex with least distance from the hull one at a time, until all vertices lie on a complex, concave hull. I realized my heuristic was a generalization that delayed "choosing" the vertex with least local distance until the distance had enough surrounding influence towards a global optimum. The film acts as a way to distribute this influence while suction is applied, in addition to providing a boundary to traverse. Measuring this film distance is only done implicitly in this case, when traversed. Simplifying it to work within Like-like rules is a practical way to approximate the model, in regards to the goal of finding the path. Practical in terms of efficiency due to possible parallelism, and hopefully no error, other than spatial discretization, due to binary values. > Along those lines, I think perhaps that the "moats" image, which is here: > > http://www.tsp.gatech.edu/gallery/igraphics/tspmoat.html > > could benefit from more explanation. How does one determine the radii of the > red circles? If there are multiple possibilities or if that is > non-deterministic, then how is it self-evident from the image (as the > caption implies) that the indicated tour (Hamiltonian path) is optimal? I can't speak for GT, nor about that picture, but you do bring up a great point about TSP instances with multiple optimal paths. I haven't experimentally tested this yet, but the model might be able to predict something about that. In the continuous case, two or more vertices that are collinear with the center of mass might produce some singularities. I've been wondering if this is where multiple possible tours arise. > You ask for suggestions on how to "coerce Python into mapping multiple > instances of Golly over parts of the rule space for parallelism". There are > two possible approaches to this: Thanks for the valuable tips. Honestly, I hadn't thought about running _actual_ multiple instances of Golly. Originally, I was hoping to just import Python's multiprocessing module and Pool map over the inner search loop, splitting up the rule space evenly across processes. This loop just reopens the file, runs some rules, and returns. However, I think I missed comprehension of Python's (or Golly's) ability for multiprocessing. Is Pool an option when running inside a Golly script, or do I need real instances of Golly somehow like Robert suggested : bgollys with shell, or Gollys each with their own copy of the script? |
From: Mark J. <mar...@gm...> - 2013-02-24 20:14:08
|
I guess unbusy beavers are not very interesting. After this, I found one that starts at gen 83 (period 13), then at gen 14 (period=15), gen 4 (period=34), and finally a whole family that start at gen 2 (period=9). Where is the line that separates chaotic from non-chaotic when you have just two or four samples to work with. There isn't. Mark. On Sun, Feb 24, 2013 at 6:39 PM, Mark Jeronimus <mar...@gm...> wrote: > I found a very 'unbusy' beaver of the 2s2c kind. This one is chaotic > for a mere 128 iterations before making a highway. Is there an even > unbusier one that's not trivial? > > {{{0,1,1},{1,1,0}},{{1,2,0},{1,4,1}}} > {{{0,1,1},{1,1,0}},{{1,8,0},{1,4,1}}} > > I define a highway as a trail pattern that doesn't start at gen 0, in > which case it would be called 'runaway'. > > Mark > > On Sat, Feb 23, 2013 at 12:33 AM, Mark Jeronimus > <mar...@gm...> wrote: >> I found an interesting 1-dimensional 2s2c turmite that builds a binary >> counter. As opposed to others, this one: >> - is 1-wide, >> - counts only upwards, not in two directions. >> >> {{{1,4,1},{1,1,0}},{{0,4,0},{0,1,1}}} >> >> Mark >> >> On Mon, Feb 18, 2013 at 9:04 PM, Mark Jeronimus >> <mar...@gm...> wrote: >>> I have a better version of Turmites! which now contains all the detection >>> routines I wanted to implement. I also implemented actual colors for the >>> turnites with more than two colors. Some bug fixes and usability additions. >>> I also managed to squeeze 50% more performance out of it (70M per second on >>> my PC) by rearranging some variables and making a queue for data to analyze. >>> >>> https://dl.dropbox.com/u/13260068/Turmites_beta1.zip >>> >>> Remember, this simulates all turmites, not just 2c2s ones. (technically up >>> to 256c256s, but untested so far for obvious reasons) >>> >>> Playing with the 'random' button, I quickly found several 2c2s rules that >>> live for hundreds of millions of generations and are quite 'round'. I also >>> noticed that rules that tend towards building highways also tend to be >>> oddly-shaped. I'm starting to think sub-billion chaotic rules may actually >>> be more rare. >>> >>> >>> Regards, >>> Mark |
From: Mark J. <mar...@gm...> - 2013-02-24 17:40:24
|
I found a very 'unbusy' beaver of the 2s2c kind. This one is chaotic for a mere 128 iterations before making a highway. Is there an even unbusier one that's not trivial? {{{0,1,1},{1,1,0}},{{1,2,0},{1,4,1}}} {{{0,1,1},{1,1,0}},{{1,8,0},{1,4,1}}} I define a highway as a trail pattern that doesn't start at gen 0, in which case it would be called 'runaway'. Mark On Sat, Feb 23, 2013 at 12:33 AM, Mark Jeronimus <mar...@gm...> wrote: > I found an interesting 1-dimensional 2s2c turmite that builds a binary > counter. As opposed to others, this one: > - is 1-wide, > - counts only upwards, not in two directions. > > {{{1,4,1},{1,1,0}},{{0,4,0},{0,1,1}}} > > Mark > > On Mon, Feb 18, 2013 at 9:04 PM, Mark Jeronimus > <mar...@gm...> wrote: >> I have a better version of Turmites! which now contains all the detection >> routines I wanted to implement. I also implemented actual colors for the >> turnites with more than two colors. Some bug fixes and usability additions. >> I also managed to squeeze 50% more performance out of it (70M per second on >> my PC) by rearranging some variables and making a queue for data to analyze. >> >> https://dl.dropbox.com/u/13260068/Turmites_beta1.zip >> >> Remember, this simulates all turmites, not just 2c2s ones. (technically up >> to 256c256s, but untested so far for obvious reasons) >> >> Playing with the 'random' button, I quickly found several 2c2s rules that >> live for hundreds of millions of generations and are quite 'round'. I also >> noticed that rules that tend towards building highways also tend to be >> oddly-shaped. I'm starting to think sub-billion chaotic rules may actually >> be more rare. >> >> >> Regards, >> Mark |
From: Robert M. <mr...@gm...> - 2013-02-24 15:26:01
|
Hello Joel, I see that this is a very involved project that you (and others at GT?) have been working on for a long time. It would help to have more of an introduction. Are there any papers on this approach? Upon what theory is it known that any type of physical simulation at all (like wave fronts, soap-bubbles, etc.) can produce candidate TSP paths? Along those lines, I think perhaps that the "moats" image, which is here: http://www.tsp.gatech.edu/gallery/igraphics/tspmoat.html could benefit from more explanation. How does one determine the radii of the red circles? If there are multiple possibilities or if that is non-deterministic, then how is it self-evident from the image (as the caption implies) that the indicated tour (Hamiltonian path) is optimal? I do like your approach, and after manually trying an example, running one through the various patterns (B12345678/S12345678, B0/S5678, B12345678/S12345678, etc.) I think I have a pretty good idea of what you are trying to do. You ask for suggestions on how to "coerce Python into mapping multiple instances of Golly over parts of the rule space for parallelism". There are two possible approaches to this: * If your Python script is running directly under the (operating system) shell, then you want to have Python launch instances of Golly. For this approach you should use the command-line Golly, which is called "bgolly". I get bgolly when I build Golly from source; I'm not sure how users get it (but others on this list can answer that). Once you have it, invoke it with no arguments for terse help (quoted below [2]). Basically you give it arguments to specify input and output files and tell it how many generations to run. The Python would need to manually inspect the output every 1 or 2 generations to perform its tests. I believe it is capable of producing pixel-bitmap output, which might be more suitable. * If instead you are running Python script *inside* Golly, then you have multiple instances of the GUI (graphical user interface) Golly running side-by-side. In this case your Python scripts cannot communicate with each other, at least not reliably[1]. Instead I would suggest that you have each Python script explore a separate, and non-overlapping, part of the search space. For example, you could number all the rules from 0 to 2^18-1 and divide this number into N pieces, where N is the number of copies of Golly. It would help to have an even distribution of rules for this test. My approach to this problem (which I have solved in the past in other projects) it to use a CRC or other quasi-random hash function to scramble things up, and thereby balance the load: import zlib NUM_CPUS = 16 # This should be the same in all instances my_cpu_id = 7 # This should be in range(0,NUM_CPUS) for bbits in xrange(512): for sbits in xrange(512): rule = 'B' for p2 in xrange(9): if bbits & 2**p2: rule += str(p2) rule += '/S' for p2 in xrange(9): if sbits & 2**p2: rule += str(p2) if zlib.crc32(rule)%NUM_CPUS == my_cpu_id: print 'testing rule: ',rule - Robert [1] Actually, you could probably have Python scripts reading and writing files, and polling the file system to coordinate each others' actions. But I don't think it's worth the effort. [2] Here is the documentation for bgolly: This is bgolly 2.5 Copyright 2012 The Golly Gang. Usage: bgolly [options] patternfile -m --generation How far to run -i --stepsize Step size -M --maxmemory Max memory to use in megabytes -2 --exponential Use exponentially increasing steps -q --quiet Don't show population; twice, don't show anything -r --rule Life rule to use -h --hashlife Use Hashlife algorithm -a --algorithm Select algorithm by name -o --output Output file (*.rle, *.mc, *.rle.gz, *.mc.gz) -v --verbose Verbose -t --timeline Use timeline --render Render (benchmarking) --progress Render during progress dialog (debugging) --popcount Popcount (benchmarking) --scale Rendering scale --autofit Autofit before each render --exec Run testing script On Sun, Feb 24, 2013 at 12:42 AM, Joel Snyder <joe...@gm...>wrote: > This is a quasi cross-posting of what I sent to a Usenet comp.theory > thread "Traveling Salesman in Life-like Cellular Automata." Google's > archive of my post can be found at > < > https://groups.google.com/group/comp.theory/browse_thread/thread/330653e980f1baaf# > > > > I'm working on encoding the traveling salesman problem into a sequence > of 2D outer-totalistic rules. Vertices are embedded into the universe > as live cells, and evolved according to this sequence with various > pausing conditions. > > The final goal is to create a completely solid curve with minimal > perimeter -- spanning all original vertices, each having at least one > dead neighbor. These conditions allow traversing a tour of the > original vertices by walking the boundary cells that have neighbors in > both the solid region and the dead space. Example optimal solid curves > are available at > <" rel="nofollow">http://www.tsp.gatech.edu/gallery/iptours/index.html> > > Attached is a script that implements part of the algorithm. So far it > produces an enlarged convex hull and "shrink wraps" the original > vertices. It's missing a vital portion: cells are set up like rows of > dominoes but still need to be collapsed properly into their minimized, > solid configuration. > > The guiding analogy is an infinitely flexible film that encases the > convex hull, deforming towards the center of mass with suction until > all vertices contact the film. In a spatially _continuous_ scenario, > large gaps between vertices should produce deep infoldings and small > gaps should see little deviation from a taut segment connecting the > vertices. Uncomment the autoupdate flag in the script to watch the > _discrete_ case leave something similar to a wake as the film passes > the vertices. > > I'm also attaching the latest search engine version I've written for > the remaining rules. This version does _not_ return correct rules, but > the script contains valuable functions like a proper code definition > of solidity and can guide future efforts. > > The search engine looks through all 2**18 rules. From early test > results, it seems unlikely to produce a minimal solid curve directly > with just one more rule, given shrink wrapped vertices from a hull > "radius" 1, 2, or 3 cells beyond the true convex hull. Note different > hull radii produce different shrink wrap wakes. > > Promising rules from those tests appeared twisted though. For > instance, try running B0123/S014 _after_ shrink wrapping vertices. > Although this isn't a _completely_ solid curve, nor spans the original > vertices for most input, its stable infoldings are nearly as intricate > as the intended output. Attached are screen captures depicting an > example evolution. > > Perhaps before applying a curve minimization rule, an intermediate > rule is needed to reorient the wake leftover from shrink wrapping. If > another rule is needed, though, searching via brute force might become > computationally expensive. Most of my tests with 2**18 rules have > taken about 1.5 hours on a 2007-era laptop. I wasn't able to coerce > Python into mapping multiple instances of Golly over parts of the rule > space for parallelism. Suggestions welcome. > > Any other feedback is highly appreciated, as well :) > -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com |
From: Joel S. <joe...@gm...> - 2013-02-24 05:42:43
|
This is a quasi cross-posting of what I sent to a Usenet comp.theory thread "Traveling Salesman in Life-like Cellular Automata." Google's archive of my post can be found at <" rel="nofollow">https://groups.google.com/group/comp.theory/browse_thread/thread/330653e980f1baaf#> I'm working on encoding the traveling salesman problem into a sequence of 2D outer-totalistic rules. Vertices are embedded into the universe as live cells, and evolved according to this sequence with various pausing conditions. The final goal is to create a completely solid curve with minimal perimeter -- spanning all original vertices, each having at least one dead neighbor. These conditions allow traversing a tour of the original vertices by walking the boundary cells that have neighbors in both the solid region and the dead space. Example optimal solid curves are available at <" rel="nofollow">http://www.tsp.gatech.edu/gallery/iptours/index.html> Attached is a script that implements part of the algorithm. So far it produces an enlarged convex hull and "shrink wraps" the original vertices. It's missing a vital portion: cells are set up like rows of dominoes but still need to be collapsed properly into their minimized, solid configuration. The guiding analogy is an infinitely flexible film that encases the convex hull, deforming towards the center of mass with suction until all vertices contact the film. In a spatially _continuous_ scenario, large gaps between vertices should produce deep infoldings and small gaps should see little deviation from a taut segment connecting the vertices. Uncomment the autoupdate flag in the script to watch the _discrete_ case leave something similar to a wake as the film passes the vertices. I'm also attaching the latest search engine version I've written for the remaining rules. This version does _not_ return correct rules, but the script contains valuable functions like a proper code definition of solidity and can guide future efforts. The search engine looks through all 2**18 rules. From early test results, it seems unlikely to produce a minimal solid curve directly with just one more rule, given shrink wrapped vertices from a hull "radius" 1, 2, or 3 cells beyond the true convex hull. Note different hull radii produce different shrink wrap wakes. Promising rules from those tests appeared twisted though. For instance, try running B0123/S014 _after_ shrink wrapping vertices. Although this isn't a _completely_ solid curve, nor spans the original vertices for most input, its stable infoldings are nearly as intricate as the intended output. Attached are screen captures depicting an example evolution. Perhaps before applying a curve minimization rule, an intermediate rule is needed to reorient the wake leftover from shrink wrapping. If another rule is needed, though, searching via brute force might become computationally expensive. Most of my tests with 2**18 rules have taken about 1.5 hours on a 2007-era laptop. I wasn't able to coerce Python into mapping multiple instances of Golly over parts of the rule space for parallelism. Suggestions welcome. Any other feedback is highly appreciated, as well :) |
From: Dean H. <dea...@ya...> - 2013-02-23 17:29:00
|
I've found a Turmite with another population growth rate: {{{1,8,0},{2,2,0},{3,2,0},{4,2,0},{1,1,0}}} This has a double base-4 counter in a pair of vertical lines, surrounded by a diamond shape. Each time the count reaches a power of 4, the Turmite moves once around the diamond, increasing its size. This increase starts in gen (4^(n+6) + 36 n^2 + 303 n + 665)/9 for n>=0, at which time the population is 2 n^2 + 22 n + 51. So the population in gen t is asymptotic to C log(t)^2, where C = 2/log(4)^2. There's an obvious pattern to the middle 3 triples in the Turmite descriptor, which can be extended. The next 4 cases are: {{{1,8,0},{2,2,0},{3,2,0},{4,2,0},{5,2,0},{1,1,0}}} {{{1,8,0},{2,2,0},{3,2,0},{4,2,0},{5,2,0},{6,2,0},{1,1,0}}} {{{1,8,0},{2,2,0},{3,2,0},{4,2,0},{5,2,0},{6,2,0},{7,2,0},{1,1,0}}} {{{1,8,0},{2,2,0},{3,2,0},{4,2,0},{5,2,0},{6,2,0},{7,2,0},{8,2,0},{1,1,0}}} For each of these, we again get O(log(t)^2) growth, but with a quadruple counter, growing both horizontally and vertically, instead of the double counter described above. We could also decrease the number of triples: {{{1,8,0},{2,2,0},{3,2,0},{1,1,0}}} {{{1,8,0},{2,2,0},{1,1,0}}} But neither of these has O(log(t)^2) growth, at least with the usual 1-cell starting pattern. Dean Hickerson |
From: Mark J. <mar...@gm...> - 2013-02-23 11:30:30
|
> Interesting, thanks. Can you post an RLE or macrocell file of just the highway so we can see how it grows? Actual highway seed: x = 13, y = 19, rule = Turmite_141110112111021120 3.A.A$2.A.A.A$3.3A$4.3A.A$3.6A$2.A.7A$.11A$4.9A$4.8A$3.2A.5A$2.10A$2. 3A.3A.A.A$12A$A.5A.4A$.11A$A.A.A.5A.A$12A$3A.6A$4AR4A2.2A! Minimzed highway seed: x = 8, y = 19, rule = Turmite_141110112111021120 2.A.A$3.A.A$2.2A$3.3A$2.3A$.A.A.A$A2.2A$3.5A$3.2A$3.A$.6A$3.A.A$3.4A$ 3.2A$3.A$3.A$3.A$3.A$3.R! Mark |
From: Dean H. <dea...@ya...> - 2013-02-23 03:42:33
|
Mostly to Mark Jeronimus: > I'm now running the 2nd spiky rule, > {{{1,4,1},{1,1,0}},{{1,1,2},{1,1,1}},{{0,2,1},{1,2,0}}}, and > although often it looks like it's getting trapped in a double-ended > blodgy-looking highway, they all eventually break, but I've > seen a very clean-cut double highway (even cleaner than those in > the 2st spiky rule) at near 11 billion gens. ... > http://ruletablerepository.googlecode.com/files/t32r141110112111021120_highway_closeup.png Interesting, thanks. Can you post an RLE or macrocell file of just the highway so we can see how it grows? I wish we understood why these rules produce such long pseudo-highways. Here's another rule with a similar mystery: {{{1,8,0},{2,2,0},{3,4,0},{4,8,0},{4,1,0}}} This one grows chaotically, but mostly in a vertical direction. It runs quite efficiently in Golly. I've run it to about gen 296 billion, at which point its bounding box is 77674 units tall and 3594 units wide. (See attached picture.) Its bounding box is usually (so far) about 20 times as tall as it is wide. Will it stay that way forever, or will it start growing the other way at some time? I wrote: > I've designed one, using 2 colors and 10 states, that produces > a Sierpinski gasket: You replied: > Nice. Though one might argue that every turmite that grows > unbounded chaotically (like the unresolved 2s2c ones) are fractal > because the boundary of the area of visited cells has fractal > dimension. That assumes that there are some that grow chaotically forever. Do we actually know that? The only way I can think of to prove that a Turmite never falls into one of the known types of predictable behaviour is if we can recognize that it's doing some sort of calculation that we know never ends, like computing the digits of pi. It might make a fractal, but it probably won't look very chaotic. |
From: Mark J. <mar...@gm...> - 2013-02-22 23:34:43
|
I found an interesting 1-dimensional 2s2c turmite that builds a binary counter. As opposed to others, this one: - is 1-wide, - counts only upwards, not in two directions. {{{1,4,1},{1,1,0}},{{0,4,0},{0,1,1}}} Mark On Mon, Feb 18, 2013 at 9:04 PM, Mark Jeronimus <mar...@gm...> wrote: > I have a better version of Turmites! which now contains all the detection > routines I wanted to implement. I also implemented actual colors for the > turnites with more than two colors. Some bug fixes and usability additions. > I also managed to squeeze 50% more performance out of it (70M per second on > my PC) by rearranging some variables and making a queue for data to analyze. > > https://dl.dropbox.com/u/13260068/Turmites_beta1.zip > > Remember, this simulates all turmites, not just 2c2s ones. (technically up > to 256c256s, but untested so far for obvious reasons) > > Playing with the 'random' button, I quickly found several 2c2s rules that > live for hundreds of millions of generations and are quite 'round'. I also > noticed that rules that tend towards building highways also tend to be > oddly-shaped. I'm starting to think sub-billion chaotic rules may actually > be more rare. > > > Regards, > Mark |
From: Mark J. <mar...@gm...> - 2013-02-22 22:56:51
|
I'm now running the 2nd spiky rule, {{{1,4,1},{1,1,0}},{{1,1,2},{1,1,1}},{{0,2,1},{1,2,0}}}, and although often it looks like it's getting trapped in a double-ended blodgy-looking highway, they all eventually break, but I've seen a very clean-cut double highway (even cleaner than those in the 2st spiky rule) at near 11 billion gens. This one was completely inside the body but it at least shows the potential to end if it ever appears outside and unobstructed. Again, it runs out of memory, now at gen 22 billion. These are snapshots of around gen 16 billion: http://ruletablerepository.googlecode.com/files/t32r141110112111021120.png http://ruletablerepository.googlecode.com/files/t32r141110112111021120_highway_closeup.png Mark On Fri, Feb 22, 2013 at 11:33 PM, Mark Jeronimus <mar...@gm...> wrote: >> I'll see if I can come up with a more memory-efficient algorithm. >> Tough it won't be as fast as Turmites!, I hope it will at least outrun >> Golly. > > I finished a program based on nested arrays, similar to the algorithm > I described before that was only 2 times faster than Golly, and was > now able to simulate 25x faster than Golly (probably because I > use nested 16x16 grids instead of nested 3x3 grids) but it still runs > out of its 1.5G memory around 5.5 billion gens (just short of the > double highway). > > But I see someone else already nicely closed in on the highway. > > Mark |
From: Mark J. <mar...@gm...> - 2013-02-22 22:34:19
|
> I'll see if I can come up with a more memory-efficient algorithm. > Tough it won't be as fast as Turmites!, I hope it will at least outrun > Golly. I finished a program based on nested arrays, similar to the algorithm I described before that was only 2 times faster than Golly, and was now able to simulate 25x faster than Golly (probably because I use nested 16x16 grids instead of nested 3x3 grids) but it still runs out of its 1.5G memory around 5.5 billion gens (just short of the double highway). But I see someone else already nicely closed in on the highway. Mark |
From: Dean H. <dea...@ya...> - 2013-02-22 21:06:13
|
Robert Munafo wrote: > On Fri, Feb 22, 2013 at 6:53 AM, Mark Jeronimus > <mar...@gm...> wrote: > First, can someone with a faster program track this Turmite > to completion?: > > {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} Actually I wrote that, not Mark. > We can plug these numbers into the following formulas: > > len = K sqrt(t) ... > K = 1.36 If the 2-way highway is the same as the one that I saw earlier, then K = 12/sqrt(78) ~ 1.35873 > The infinite periodic portion of the double-ended highway of > turmite {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} > appears at about generation 6,527,150,000. Thanks! |
From: Robert M. <mr...@gm...> - 2013-02-22 20:41:25
|
The infinite periodic portion of the double-ended highway of turmite {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} appears at about generation 6,527,150,000. >> On Fri, Feb 22, 2013 at 6:53 AM, Mark Jeronimus <mar...@gm... wrote: > First, can someone with a faster program track this Turmite to > completion?: > > {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} > > So far they've all run into other stuff and stopped, but probably > one will eventually be produced that grows forever. I've run it for 5.556 > billion gens. > >>>Robert Munafo wrote: >>>> Here's a picture at 3.23e10 generations: >>>> >>>> mrob.com/pub/comp/dqca/images/Turmite_182112120111082181_3.23e10.png >>>> >>>> I verified that the double-ended highway at the top is growing. In the >>>> X direction it extends from -121116 to +97081. If you have a formula for >>>> the rate of growth of these highways, you can extrapolate backwards to >>>> figure out when it started. The simulation from gen 0 took 10 hours on my >>>> machine, with Golly's memory usage set to 15GB (15000 MB). -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com |
From: Robert M. <mr...@gm...> - 2013-02-22 20:06:06
|
With Tom's help I figured out that the Timeline in Golly works in a lot of situations that I had never tried. The double-ended highway of turmite {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} begins growing between generations 6,527,155,712 and 6,529,252,864. I'm now narrowing it down a bit further. On Fri, Feb 22, 2013 at 12:38 PM, Tom Rokicki <ro...@gm...> wrote: > The timeline works really nicely for this, by the way. -tom > > On Fri, Feb 22, 2013 at 8:55 AM, Robert Munafo <mr...@gm...> wrote: > >> On Fri, Feb 22, 2013 at 6:53 AM, Mark Jeronimus <mar...@gm... >>>> > wrote: >>>> >>>>> > First, can someone with a faster program track this Turmite to >>>>> completion?: >>>>> > >>>>> > {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} >>>>> > >>>>> > So far they've all run into other stuff and stopped, but probably >>>>> one will eventually be produced that grows forever. I've run it for 5.556 >>>>> billion gens. >>>>> >>>> >>>> Here's a picture at 3.23e10 generations: >>>> >>>> mrob.com/pub/comp/dqca/images/Turmite_182112120111082181_3.23e10.png >>>> >>>> I verified that the double-ended highway at the top is growing. In the >>>> X direction it extends from -121116 to +97081. If you have a formula for >>>> the rate of growth of these highways, you can extrapolate backwards to >>>> figure out when it started. The simulation from gen 0 took 10 hours on my >>>> machine, with Golly's memory usage set to 15GB (15000 MB). >>>> >>> -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com |
From: Tom R. <ro...@gm...> - 2013-02-22 17:38:56
|
The timeline works really nicely for this, by the way. -tom On Fri, Feb 22, 2013 at 8:55 AM, Robert Munafo <mr...@gm...> wrote: > A little error at the end, I should have said 6.6 billion. So only a > billion more than Mark ran it. I've reset Golly and am running it again to > get a more accurate measurement of when the final double highway starts. > > On Fri, Feb 22, 2013 at 11:13 AM, Robert Munafo <mr...@gm...> wrote: > >> I ran the pattern a bit more and took measurements to establish how >> quickly the double-ended highway was growing: >> [...] >> Which means the double-ended highway has been growing for about >> 25,980,000,000 gens, meaning it started at about gen. 6.6e10 or 66 billion. >> >> On Fri, Feb 22, 2013 at 10:39 AM, Robert Munafo <mr...@gm...> wrote: >> >>> On Fri, Feb 22, 2013 at 6:53 AM, Mark Jeronimus < >>> mar...@gm...> wrote: >>> >>>> > First, can someone with a faster program track this Turmite to >>>> completion?: >>>> > >>>> > {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} >>>> > >>>> > So far they've all run into other stuff and stopped, but probably one >>>> will eventually be produced that grows forever. I've run it for 5.556 >>>> billion gens. >>>> >>> >>> Here's a picture at 3.23e10 generations: >>> >>> mrob.com/pub/comp/dqca/images/Turmite_182112120111082181_3.23e10.png >>> >>> I verified that the double-ended highway at the top is growing. In the X >>> direction it extends from -121116 to +97081. If you have a formula for the >>> rate of growth of these highways, you can extrapolate backwards to figure >>> out when it started. The simulation from gen 0 took 10 hours on my machine, >>> with Golly's memory usage set to 15GB (15000 MB). >>> >> > -- > Robert Munafo -- mrob.com > Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - > mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com > > > > ------------------------------------------------------------------------------ > Everyone hates slow websites. So do we. > Make your web apps faster with AppDynamics > Download AppDynamics Lite for free today: > http://p.sf.net/sfu/appdyn_d2d_feb > _______________________________________________ > Golly-test mailing list > Gol...@li... > https://lists.sourceforge.net/lists/listinfo/golly-test > > -- -- http://cube20.org/ -- http://golly.sf.net/ -- |
From: Robert M. <mr...@gm...> - 2013-02-22 16:56:05
|
A little error at the end, I should have said 6.6 billion. So only a billion more than Mark ran it. I've reset Golly and am running it again to get a more accurate measurement of when the final double highway starts. On Fri, Feb 22, 2013 at 11:13 AM, Robert Munafo <mr...@gm...> wrote: > I ran the pattern a bit more and took measurements to establish how > quickly the double-ended highway was growing: > [...] > Which means the double-ended highway has been growing for about > 25,980,000,000 gens, meaning it started at about gen. 6.6e10 or 66 billion. > > On Fri, Feb 22, 2013 at 10:39 AM, Robert Munafo <mr...@gm...> wrote: > >> On Fri, Feb 22, 2013 at 6:53 AM, Mark Jeronimus <mar...@gm... >> > wrote: >> >>> > First, can someone with a faster program track this Turmite to >>> completion?: >>> > >>> > {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} >>> > >>> > So far they've all run into other stuff and stopped, but probably one >>> will eventually be produced that grows forever. I've run it for 5.556 >>> billion gens. >>> >> >> Here's a picture at 3.23e10 generations: >> >> mrob.com/pub/comp/dqca/images/Turmite_182112120111082181_3.23e10.png >> >> I verified that the double-ended highway at the top is growing. In the X >> direction it extends from -121116 to +97081. If you have a formula for the >> rate of growth of these highways, you can extrapolate backwards to figure >> out when it started. The simulation from gen 0 took 10 hours on my machine, >> with Golly's memory usage set to 15GB (15000 MB). >> > -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com |
From: Robert M. <mr...@gm...> - 2013-02-22 16:14:17
|
I ran the pattern a bit more and took measurements to establish how quickly the double-ended highway was growing: at gen 32,323,703,360: -121,116 to +97,081 +2097152 at gen 32,325,800,512: -121,119 to +97,086 +8388608 at gen 32,334,189,120: -121,138 to +97,103 (len 218241) +67108864, len +282, growth rate +4.20e-6 at gen 32,401,297,984: -121,278 to +97,245 (len 218523) +201326592, len +850, growth rate +4.22e-6 at gen 32,602,624,576: -121,704 to +97,669 (len 219373) We can plug these numbers into the following formulas: len = K sqrt(t) len' = K/(2*sqrt(t)) 219373 = K sqrt(t) 4.22e-6 = K/(2*sqrt(t)) Multiply the two together to get the unknown K: 0.9261918564637 = K^2/2 K = 1.36 Then plug back into the first formula to get the unknown t: t = (219373/1.36)^2 = 2.598e10 Which means the double-ended highway has been growing for about 25,980,000,000 gens, meaning it started at about gen. 6.6e10 or 66 billion. On Fri, Feb 22, 2013 at 10:39 AM, Robert Munafo <mr...@gm...> wrote: > On Fri, Feb 22, 2013 at 6:53 AM, Mark Jeronimus <mar...@gm...> > wrote: > >> > First, can someone with a faster program track this Turmite to >> completion?: >> > >> > {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} >> > >> > So far they've all run into other stuff and stopped, but probably one >> will eventually be produced that grows forever. I've run it for 5.556 >> billion gens. >> > > Here's a picture at 3.23e10 generations: > > mrob.com/pub/comp/dqca/images/Turmite_182112120111082181_3.23e10.png > > I verified that the double-ended highway at the top is growing. In the X > direction it extends from -121116 to +97081. If you have a formula for the > rate of growth of these highways, you can extrapolate backwards to figure > out when it started. The simulation from gen 0 took 10 hours on my machine, > with Golly's memory usage set to 15GB (15000 MB). > -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com |
From: Robert M. <mr...@gm...> - 2013-02-22 15:40:20
|
On Fri, Feb 22, 2013 at 6:53 AM, Mark Jeronimus <mar...@gm...> wrote: > > First, can someone with a faster program track this Turmite to > completion?: > > > > {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} > > > > So far they've all run into other stuff and stopped, but probably one > will eventually be produced that grows forever. I've run it for 5.556 > billion gens. > Here's a picture at 3.23e10 generations: mrob.com/pub/comp/dqca/images/Turmite_182112120111082181_3.23e10.png I verified that the double-ended highway at the top is growing. In the X direction it extends from -121116 to +97081. If you have a formula for the rate of growth of these highways, you can extrapolate backwards to figure out when it started. The simulation from gen 0 took 10 hours on my machine, with Golly's memory usage set to 15GB (15000 MB). -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com |
From: Mark J. <mar...@gm...> - 2013-02-22 11:53:52
|
> First, can someone with a faster program track this Turmite to completion?: > > {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} > > So far they've all run into other stuff and stopped, but probably one will eventually be produced that grows forever. I've run it for 5.556 billion gens. I'm afraid to say that Turmites! ran out of memory near gen 0.13 billion. This rule grows at a speed I've never seen before (Except when trapped in highways). Note: Turmites! Beta1 crashes when trying this rule because of a bug in the rule-checker (in fact, for all rules with more states than colors). > Another Turmite that produces even longer spikes is > > {{{1,4,1},{1,1,0}},{{1,1,2},{1,1,1}},{{0,2,1},{1,2,0}}} > > But I've never seen this one make a highway that could grow forever, so I won't try to guess its fate. I've run it for 9.796 billion gens. This one grows slightly slower but still way too fast. Out of memory near gen 0.63 billion. I'll see if I can come up with a more memory-efficient algorithm. Tough it won't be as fast as Turmites!, I hope it will at least outrun Golly. > Second, has anyone run across a Turmite that produces a fractal? I've designed one, using 2 colors and 10 states, that produces a Sierpinski gasket: Nice. Though one might argue that every turmite that grows unbounded chaotically (like the unresolved 2s2c ones) are fractal because the boundary of the area of visited cells has fractal dimension. > Finally, what asymptotic population growth rates can a Turmite have? For random Turmites, I've seen 4 different provable growth rates quite often: There's a fundamental difference between 'population' and area. Population is by definition all cells which aren't of state 0, which is useless in the context of turmites. Area, which I define as the number of unique cells visited by the turmite, is. Hence, I always use the term area in the context of turmites. I thought about growth rates too, because it's indicative of how 'random' a turmite is, but it's very difficult. Take for example the chaotic unresolved 2s2c rules. Some grow faster than others. The reason for this is that some turmites like boundaries so they tend to grow faster, while others dislike boundaries and immediately U-turn when hitting it. In the center, the path can be assumed to be analogous to a Random Walk, which for some reason (probably because reflecting of the boundaries) visits cells near the origin proportionally more often than cells around it. A prime example of this center-visitness is Ed#11 "framed computer art" {{{1, 8, 0}, {1, 2, 1}}, {{0, 2, 0}, {0, 8, 1}}}, with the following visit-count maps in linear or logarithmic domains (1 billion gens): http://ruletablerepository.googlecode.com/files/t22r180121020081_lin.png http://ruletablerepository.googlecode.com/files/t22r180121020081_log.png All turmites which grow radially, and approximately isotropically, exhibit this behavior. One could probably calculate the growth rate by plotting the standard deviation against the gen and fitting it to a function, which can be either of linear, power, logarithmic, log-log or even more complex. Regards, Mark |
From: Dean H. <dea...@ya...> - 2013-02-22 04:31:27
|
I tried to send this yesterday, but it was too big because of two attached pictures, so I got a message saying it was being held until the list moderator can review it for approval. I've heard nothing further, so I'm sending it again without the pictures. I can no longer access the web page to cancel the original, so maybe it will show up eventually. Anyway, here's the message, slightly edited from the original: First, can someone with a faster program track this Turmite to completion?: {{{1,8,2},{1,1,2}},{{1,2,0},{1,1,1}},{{0,8,2},{1,8,1}}} It produces long horizontal and vertical spikes with bumpy edges; they can grow hundreds of units long before the Turmite changes direction. I confess that I don't understand why they grow so long. A few times the Turmite has produced complicated 2-way highways that could grow forever, like this one: x = 20, y = 12, rule = Turmite_182112120111082181 3A$3A2.4A$12A$14A$15A$18A$2.17A$2.17A$4.5AU10A$11.9A$12.8A$13.3A! So far they've all run into other stuff and stopped, but probably one will eventually be produced that grows forever. I've run it for 5.556 billion gens. Another Turmite that produces even longer spikes is {{{1,4,1},{1,1,0}},{{1,1,2},{1,1,1}},{{0,2,1},{1,2,0}}} But I've never seen this one make a highway that could grow forever, so I won't try to guess its fate. I've run it for 9.796 billion gens. Second, has anyone run across a Turmite that produces a fractal? I've designed one, using 2 colors and 10 states, that produces a Sierpinski gasket: {{{1,4,0},{1,2,6}}, {{0,2,2},{1,2,3}}, {{0,2,4},{1,2,5}}, {{0,2,5},{1,2,4}}, {{0,4,1},{0,0,0}}, {{1,4,1},{1,8,6}}, {{0,2,7},{0,0,0}}, {{1,2,8},{0,0,0}}, {{0,1,8},{1,8,9}}, {{1,4,9},{1,1,1}}} (Note that some of the triples are {0,0,0}. Those indicate state-color combinations that never occur, and could be replaced by any valid triples.) This produces the fractal a row at a time, by setting each cell to the XOR of the cells to its north and northwest. Probably the number of states could be reduced a bit by being slightly more clever. But Turmites are smarter than I am, so I'm guessing that there's something much simpler. Third, for {{{2,2,0},{0,4,0},{1,8,0}}}, gen 276 is identical to gen 0. Are there Turmites that have larger periods, starting at gen 0? Finally, what asymptotic population growth rates can a Turmite have? For random Turmites, I've seen 4 different provable growth rates quite often: Oscillators have constant or oscillating population. E.g. {{{2,4,0},{1,8,0},{1,2,0}}} has population 145 for t>=629. 1-way highways have population proportional to t. E.g. {{{1,1,0},{0,1,0}}} has population t+1. 2-way highways have population proportional to sqrt(t). E.g. {{{1,4,0},{1,1,0}}} has population ~ sqrt(2t). Binary counters usually have populations which are sawtooth functions. E.g. {{{1,2,0},{0,1,0}}} has population 5 in gen 2^n-5 for n>=4, and population 4*n in gen 2^(n+3) - 4*n - 9 for n>=2. This is not so common, but easily constructed: Binary counters can also have population proportional to log(t). E.g. {{{1,2,0},{2,1,0},{1,2,0}}} has population 4n in gen 2^(n+2) for n>=2. The Sierpinski gasket Turmite has population between A * t^(log(3)/log(4)) and B * t^(log(3)/log(4)) for some positive constants A and B which I haven't tried to compute. By design and accident, I've found Turmites with two other growth rates. First, I built one with population proportional to t^(1/3); population P first occurs in gen (2 P^3 + 3 P^2 - 17 P + 12)/6: {{{1,1,1},{1,1,0}},{{1,4,3},{0,4,2}},{{0,4,0},{1,1,2}},{{0,1,0},{0,4,2}}} I thought about building one for t^(1/4), and decided it would be more complicated than I wanted to deal with. But while playing around with random modifications of the t^(1/3) rule, I was surprised to find that this one with that population growth; if P is even, then population P first occurs in gen (P^4 - 3 P^3 + 26 P^2 - 12 P - 48)/24: {{{1,1,1},{1,1,0}},{{1,4,3},{0,4,2}},{{0,4,0},{1,1,2}},{{0,4,2},{0,1,1}}} And here's another t^(1/4) rule, which produces a symmetric cross: {{{1,1,1},{1,1,0}},{{1,4,3},{0,4,2}},{{0,4,0},{1,1,2}},{{1,8,1},{0,1,1}}} For this one, if P is divisible by 4 then population P first occurs in gen (P^4 + 2 P^3 + 56 P^2 - 80 P)/192. Dean Hickerson |
From: Dave G. <dav...@gm...> - 2013-02-21 15:28:37
|
Oddly enough, the week before these multi-colored Life rules started showing up on golly-test, I had just written my own rule table for a four-colored Life variant, for an art project I'm helping out with. (Art imitates Life -- or is it the other way around?) I wanted to end up with patches of persistent color, even in the background areas, so I put in four extra OFF states as well as the four ON states. There's a bigger bias toward color stability in this version: if a cell was previously ON as a particular color, it will stay that color when it comes on again. It only switches allegiance if all three neighbors are the same color. This means that small moving objects like spaceships or gliders generally gravitate toward a single color, and thus leave a clear single-color trail. For this project I wasn't too concerned with maintaining strict symmetry groups. If a cell was never previously ON, I basically pick a neighbor color at random for the new birth cell. It always seemed a little odd to have the fourth unrepresented color show up if there are three different colors to choose from, so I figured I'd try having the color always come from one of the parents. If anyone's interested, it shouldn't be too hard to patch up the attached rule table to follow more standard four-color Life rules. Basically you'd end up with a LifeColorHistory rule. There wouldn't be anything mathematically new, unless you kept the bias toward keeping the same color when an OFF cell turns back on. But you can get some interesting visual effects in signal-circuitry patterns, with lots of gliders leaving multicolored trails. Keep the cheer, DaveG |
From: Andrew T. <an...@tr...> - 2013-02-21 00:56:05
|
Me: > - Modify the scripts in Python/Rule-Generators to create .rule files > rather than .tree + .icons. I've finished changing all those scripts. The bulk of the work is done by a new routine called ConvertTreeToRule in glife/RuleTree.py. This allowed minimal changes to the existing scripts. If ConvertTreeToRule sees an existing .rule file it will only update the @TREE data. This avoids clobbering any icon/color info or other changes you might have added to the .rule file. (In particular, it lets you include the Python transition function in the documentation section of a .rule file created by make-ruletree.py.) The next step is to create a pair of scripts (probably called icon-importer.py and icon-exporter.py) that will make it easy to use Golly as an icon editor. Andrew |
From: Tom R. <ro...@gm...> - 2013-02-20 03:02:03
|
At the last Maker Faire in the Bay Area, I walked around with the four-color life described below on a small grid (I think 128x96) using the Propeller microcontroller and small OLED. It garnered a lot of attention. I used a torus and random initial positions. I mocked it up in HTML5 before coding it on the microcontroller; the size of the grid was chosen to allow people to see roughly what was going on from a distance yet provide enough space to yield interesting configurations. Some people didn't want to stop watching . . . it was much like I felt when I first saw Life running on a video display back at IIT probably about 1974. (Many thanks to whoever that anonymous grad student was, who was showing it off and handing out copies of the Scientific American article; you really changed my life.) -tom On Tue, Feb 19, 2013 at 5:57 PM, Robert Munafo <mr...@gm...> wrote: > On Tue, Feb 19, 2013 at 8:10 PM, Don Woods <do...@ic...> wrote: > > How does the 4-color >> variant work? If three all-different colors combine to spawn a new >> live cell, does it get the fourth color? > > > Yes, it's the most obvious way to break the tie and be fair, and also keep > the highest symmetry-group. (There are also ways to resolve the tie based > on the geometrical arrangement of the three neighbor cells: If only one is > diagonal, then its color prevails; similarly if only one is orthogonal; and > if all three parent-neighbors are orthogonal, the color opposite the blank > spot would prevail, and similarly the the 3-diagonal case. This approach > allows us to make games with 3 colors, or with 5 or more.) > > >> If so, it would be nice if >> the name suggested something related to that, where a concentration of >> "type" (color, race, etc.) produces more of that type, but a diversity >> of types produces more diversity. >> > > Well, I called used the word "voting" because of the similarity to voting > models and simulated annealing and I called the 2-color version "US > Edition: Red State vs. Blue State". > > Extending the political analogy, I called the 4-color version "European > edition: Socialists, Greens, Liberals and Conservatives". Here's the > description: > > "A variant of Life with four ON states (red, yellow, green and blue) > When a new cell is born, it gets the colour of the majority of > its neighbours. If there is no majority, it picks the colour that is > different from all three live neighbours. > Once born, cells remain of the same colour until they die." > > The allegorical connections to politics are pretty simple: > > * Children tend to take on the political affiliation of the majority of > the adults around them, > > * People tend to stay the same colour (political orientation) until they > die, and > > * In multi-party systems (like in Europe), when there is no simple > majority, the various parties need to form a coalition in order to form a > government, and this process often results in a de-facto "fourth party". > Also, people who are displeased with the ineffectiveness of the three > biggest parties will often switch to another party just out of desperation > or as a political act of protest. > > Alas, "Hybrid Vigor" doesn't really capture the flavor of the rule. >> "Melting Pot" describes the diversity of inputs but tends to imply the >> society evolves to become homogeneous. (If that's what happens to *most* >> starting states, that name could work.) >> > > It does seem that each species survives pretty well. The > three-different-colors-spawning-a-4th rule doesn't seem to get triggered > very often, except in the first few generations from an initial random > starting pattern. > > > Frankly, Immigration-4 is fine, too. > > I personally would like to do that. I want to use your name for the > 3-state (2-color) game, and there's a convention in Golly to try to have > names of related rules start with a related word (or first several letters). > > > (But Voter-4-Life felt wrong. The usual "4-Life" phrase would be > Dictator-4-Life. :-) > > Yes, I thought it was kind of a poor name too. Sometimes I make up these > names just as a place-holder. > > -- > Robert Munafo -- mrob.com > Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - > mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com > > > > ------------------------------------------------------------------------------ > Everyone hates slow websites. So do we. > Make your web apps faster with AppDynamics > Download AppDynamics Lite for free today: > http://p.sf.net/sfu/appdyn_d2d_feb > _______________________________________________ > Golly-test mailing list > Gol...@li... > https://lists.sourceforge.net/lists/listinfo/golly-test > > -- -- http://cube20.org/ -- http://golly.sf.net/ -- |