Unproven conjectures

[UnbihexiumFan]

Conjecture: Life is omnidirectional.
There exists an elementary spaceship for every direction and every speed.
Note: I am probably not the first one to come up with this.

Counterexample: c/3d

[NNlk05]

Conjecture: Life is omnidirectional.
There exists an elementary spaceship for every direction and every speed.
Note: I am probably not the first one to come up with this.

Counterexample: c/3d

I meant Life has every slope. Sorry but I don't have time to edit the post.

[dvgrn]

I meant Life has every slope. Sorry but I don't have time to edit the post.

If you remove the "every speed" part, it doesn't seem as if that's an unproven conjecture. For any (x,y) offset, we could use existing technology (e.g., slsparse) to compile a self-constructing spaceship that builds a copy of itself at some (kx, ky) distance, and then self-destructs.

EDIT: Right, see below, "elementary" is part of the original spec, just not part of the above re-statement. That seems like it's going to be a mighty tough conjecture to prove (or disprove) in Life, but it's certainly unproven right now!

[UnbihexiumFan]

that wouldn't be elementary, though.

EDIT: I think the only rules which can be proven to have spaceships of every slope are those which have adjustable elementary ships.

Side question: is there any rule which has a family of elementary ships with adjustable slopes like there is families with adjustable speeds? If no such rule is known I conjecture the answer is yes.

[WhiteHawk]

conjecture: any orthogonal speed can be achieved with at most 4 cells in isotropic non-totalistic rules with standard moore neighborhood - I think this has been proven for speeds of the form 1/m (m being any integer greater than or equal to 1 - 1c/m would technically also be right, where c is speed of light)

Also, is there a similar proof for diagonals of the form 1c/m

[Anivec]

Conjecture 1: a self forcing still life patch must decay fully in one generation under cell "alive<->dead" inversion, excluding cells outside of the patch and cells on the perimeter. A related statement of this is if the patch is placed on a finite grid that has a bounding box larger than the patch, and all the cells on the grid are inverted, the result decays in a single generation. The converse, "a still life patch that decays in one generation under inversion is self forcing", is not necessarily true, but it does give a hint to what one may look like.
Conjecture 2: A self forcing still life patch must have a density that is greater than or equal to some number n. This does not account for the area the patch isn't in. What are the upper and lower bounds for this number?
Conjecture 3: Is the resulting pattern of the self forcing patch after inversion a Garden of Eden?

[yyh_baboon]

Conjecture 1: a self forcing still life patch must decay fully in one generation under cell "alive<->dead" inversion, excluding cells outside of the patch and cells on the perimeter. A related statement of this is if the patch is placed on a finite grid that has a bounding box larger than the patch, and all the cells on the grid are inverted, the result decays in a single generation. The converse, "a still life patch that decays in one generation under inversion is self forcing", is not necessarily true, but it does give a hint to what one may look like.
Conjecture 2: A self forcing still life patch must have a density that is greater than or equal to some number n. This does not account for the area the patch isn't in. What are the upper and lower bounds for this number?
Conjecture 3: Is the resulting pattern of the self forcing patch after inversion a Garden of Eden?

Conj.2:Upper bound is 4/9(which has been demonstrated by the original self-forcing patch)
Conj.2a:the lowest density bound is also 4/9.
conj.2b:for every 6x6 region completely inside the patch, there must be at least 16 live cells.

[eRroR_6o6]

Conjecture, similar to Coolout: For every pattern, you can either add a finite amount of cells to stabilize it into a still life, or you can't stabilize it into a still life at all.

In other words: Every p1 agar is stabilizable.

[PK22]

I rewrote my 2G destruction searching code in C++ to remove the Python overhead (plus the HTTP delay), and I'm now 95% sure that all 25-cell still lifes have a 2G destruction.
The program doesn't check rewindibility, but it does check that the population = (SL population) + 10 in generations 0 and 1.

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>
#include <random>
#include <vector>
#include <ctime>
#include <cstdint>
#include <cstdlib>
#include "lifelib/pattern2.h"

int numgliders = 2;
//Modify to match your computer's number of threads, or how many instances you are running:
int cores = 12;
std::string getrle(apg::pattern pat){
    std::ostringstream ss;
    pat.write_rle(ss);
    std::string s = ss.str();
    return s;
}
void assemblecollision(apg::lifetree<uint32_t, 1>& lt, const std::vector<apg::pattern> gliders, const std::string apgcode) {
    int32_t loops = 0;
    apg::pattern pt(&lt, apgcode, "b3s23");
    int ptpop = pt.totalPopulation();
    apg::pattern fullpt(&lt, apgcode, "b3s23");
    int i;
    while (0 == 0) {
        fullpt = apg::pattern(&lt, apgcode, "b3s23");
        apg::pattern gliderset(&lt, "b!", "b3s23");
        for (i = 0; i < numgliders; i++) {
            int glider = rand() % 16;
            int x = (rand() % 24) + 8;
            int y = (rand() % 24) + 8;
            switch(glider%4) {
                case 0:
                    x = -x;
                    y = -y;
                    break;
                case 1:
                    x = -x;
                    break;
                case 2:
                    break;
                case 3:
                    y = -y;
                    break;
                default:
                    break;
            }
            apg::pattern newglider = gliders[glider];
            newglider = newglider.shift(x, y);
            gliderset += newglider;
        }
        fullpt += gliderset;
        apg::pattern evpt = fullpt[150];
        if (evpt.totalPopulation() == 0) {
            if (fullpt.totalPopulation() == ptpop + numgliders * 5 and fullpt[1].totalPopulation() == ptpop + numgliders*5) {
                break;
            }
        }
        loops++;
        if (loops > 1000000) {
            std::cerr << "Unable to destroy " << apgcode << "!!!" << std::endl;
            return;
        }
    }
    //std::cout << getrle(fullpt) << std::endl;
}
int main(int argc, char* argv[]) {
    srand(time(0));
    apg::lifetree<uint32_t, 1> lt(1000);
    //Assemble a vector of the 16 unique gliders:
    apg::pattern glider(&lt, "bob$bbo$ooo!", "b3s23");
    apg::pattern glider2 = glider[0];
    std::vector<apg::pattern> gliders;
    std::vector<std::string> transformations = {"identity", "rot90", "rot180", "rot270"};
    int i, j;
    for (i = 0; i < 4; i++) {
        for (auto j : transformations) {
            glider2 = glider[i];
            glider2 = glider2.transform(j, 0, 0);
            gliders.push_back(glider2);
        }
    }
    if (argc < 3) {
        std::cout << "Usage: main <file> <index>" << std::endl;
        return 0;
    }
    std::string line;
    std::string filename(argv[1]);
    std::ifstream file(filename);
    int index = std::stoi(argv[2]);
    int32_t destroyed = 0;
    while (std::getline(file, line)) {
        if (line.length() > 3 and (destroyed % cores == index) ) {
            assemblecollision(lt, gliders, line);
        }
        destroyed += 1;
        
        if (destroyed%10000 == 0 and index == 0) {
            std::cout << "Destroyed " << destroyed << " still lifes." << std::endl;
        }
    }
    file.close();
}

It should ideally be run with a shell script such as the following:

Code: Select all

#!/bin/bash
./main $1 0 &
./main $1 1 &
./main $1 2 &
./main $1 3 &
./main $1 4 &
./main $1 5 &...

Searching all 25-bit still lifes took about 6-8 hours on my machine (I wasn't there when the search finished).

If anyone has suggestions for improvements to the algorithm or more computing power than me to search 26+ bit SL, please let me know.

[NNlk05]

*snip*
...more computing power than me to search 26+ bit SL, please let me know.

If you are willing to spend some money, compute comes pretty cheap these days, I just checked with one provider (vast.ai), you can get a high tier AMD CPU for about USD$0.03 an hour.

[vilc]

Here is an attempt at giving a more formal definition of some problems on general construction vs. glider construction. Define a construction of a pattern A_0 to be a sequence of patterns (A_n) for n >= 0 such that :
- for all positive n, A_n is a predecessor of A_{n-1}
- the patterns (A_n) have uniformly bounded population
- every cell in the plane is on at most a finite number of times in the sequence (A_n)

A valid glider synthesis of A_0 implies a construction. Is the converse true? Are there patterns with a construction but no spaceship synthesis?
This definition can be generalised naturally in any rule with a "quiescent" state (a state which remains the same when surrounded by like neighbours). Can this question be answered in some rule with spaceships?

[MDA]

I conjecture that, in 2-state INT rules, every puffer, rake, or replicator not based on spaceships can be corderized in at most two engines without supporting spaceships if the rule in which they exist allows spaceships.

It seems to me like the only way to solve this conjecture is to find a counterexample.

[dl-rs]

I conjecture that, in 2-state INT rules, every puffer, rake, or replicator not based on spaceships can be corderized in at most two engines without supporting spaceships if the rule in which they exist allows spaceships.

It seems to me like the only way to solve this conjecture is to find a counterexample.

I think this is almost certainly not true. For the rule B2a3r/S that I engineered just now:

Code: Select all

x = 3, y = 2, rule = B2a3r/S
o$obo!

The domino is an obvious rep. I would delete this message if, by all means, anybody manages to corderize it within 2 engines(if it can be corderized at all).

[NNlk05]

Conjecture: There exists a strict still life that when hit by a glider in a way, emits a glider 90º relative to input and regenerates itself (ie: glider reflector) .
Had anyone checked?

[Sokwe]

Conjecture: There exists a strict still life that when hit by a glider in a way, emits a glider 90º relative to input and regenerates itself (ie: glider reflector) .
Had anyone checked?

There no doubt exists a strict still life composed of connected fuses that collapses into a universal constructor that reconstructs itself, but this might be impractical to actually build. The problem with finding a small strict still life reflector is that almost all of our stable G-to-X reactions rely on a bait still life that can't be a part of a larger strict still life. The only baitless reaction I can recall is the following G-to-pi by Mitchell Riley (with stator modified to form a single strict still life):

Code: Select all

x = 16, y = 15, rule = B3/S23
6bo$7bo$5b3o3b2ob2o$11b2obo$14bo$2o12b2o$o2bob2o8bo$b3obo3b2o3bo$5bo3b
obobo$b3ob3obob2o$o2b2o3bo$bo4b2o$2b3obo$4bobo$5bo!

Unfortunately, the output pi appears to be too close to the catalytic still life to be usable.

[dl-rs]

Is it theoretically true that for CGOL, we can construct a pattern such that it's population grows by a rate of a function consisting of n, positive integers, and the 7 basic operations, such that it is between 0 and n^2? (e.g.n/log4log3(n))
I think most trivial cases are pretty ovbious. Note, if it is possible, can the same be proven for the bounded box area?

[Ohhhhhhhhh]

conjecture: any orthogonal speed can be achieved with at most 4 cells in isotropic non-totalistic rules with standard moore neighborhood - I think this has been proven for speeds of the form 1/m (m being any integer greater than or equal to 1 - 1c/m would technically also be right, where c is speed of light)

Also, is there a similar proof for diagonals of the form 1c/m

There is this problem that m can have infinite choices but there are only a finite number of isotropic non-totalistic rules with standard moore neighborhood. So the remaining work is to show that there are also a finite number of <=4 cell constellations to make it a spaceship in any such rules. I believe that the cells cannot be seperated too far apart, otherwise they will not interact or if they still interact it will be explosive (such as rules having a B1 or B2) and cannot form a spaceship. If this is true the conjecture is disproven since a finite number of spaceship choices cannot obtain an infinite number of orthogonal speeds.

[WhiteHawk]

conjecture: any orthogonal speed can be achieved with at most 4 cells in isotropic non-totalistic rules with standard moore neighborhood - I think this has been proven for speeds of the form 1/m (m being any integer greater than or equal to 1 - 1c/m would technically also be right, where c is speed of light)

Also, is there a similar proof for diagonals of the form 1c/m

There is this problem that m can have infinite choices but there are only a finite number of isotropic non-totalistic rules with standard moore neighborhood. So the remaining work is to show that there are also a finite number of <=4 cell constellations to make it a spaceship in any such rules. I believe that the cells cannot be seperated too far apart, otherwise they will not interact or if they still interact it will be explosive (such as rules having a B1 or B2) and cannot form a spaceship. If this is true the conjecture is disproven since a finite number of spaceship choices cannot obtain an infinite number of orthogonal speeds.

I was thinking there might be an adjustable ship of some sort that would permit proof of this concept. I could be wrong and the low bound may be 5 cells, but I think whoever runs 5S may have some partial answer

[Ohhhhhhhhh]

Here is an attempt at giving a more formal definition of some problems on general construction vs. glider construction. Define a construction of a pattern A_0 to be a sequence of patterns (A_n) for n >= 0 such that :
- for all positive n, A_n is a predecessor of A_{n-1}
- the patterns (A_n) have uniformly bounded population
- every cell in the plane is on at most a finite number of times in the sequence (A_n)

A valid glider synthesis of A_0 implies a construction. Is the converse true? Are there patterns with a construction but no spaceship synthesis?
This definition can be generalised naturally in any rule with a "quiescent" state (a state which remains the same when surrounded by like neighbours). Can this question be answered some rules with spaceships?

This is really hard. There are no easy proof for a pattern to be non-glider-constructible, except Garden of Edens, but obviously these patterns do not have any constructions too.
One property of your definition of Construction is that we can choose any configuration C and select a sufficiently large n such that there are no on cells in C for all A_m where m >= n, because you just need n not less than the maximum generation of any cells on in C that the cell is off before that (finite set of positive integers has maximum). This might be useful since it requires the Construction to be as far as you need before a big enough number of generations. This along with the uniformly bounded population rule may suffice to show something significant since if the pattern is not a spaceship, this finite number of cells are not expected to 'travel' far enough to reach each other. But the 23 cell quadratic growth thing actually asks another question about whether these cells could be deliberately placed such that a puffer or other mechanics are generated and produced the pattern before clearing its debris. However with the finite on rule this is also not likely to be... and a puffer or rake or any infinite growth cannot exist by the population bound rule. I feel these restrictions for such a Construction already implies that any Construction is already a spaceship synthesis of the target pattern. The question left here is whether all spaceships can be glider synthesized? Which is stronger than the proposition by now and sounds unlikely. I mean I believed I've seen deliberate construction of spaceship in CGoL or other rules that does not have any other predecessors except the periodically repeating patterns of itself.
Anyway this is definitely nontrivial and should be investigated further. It also looks quite like a math olympiad problem...

[Ohhhhhhhhh]

conjecture: any orthogonal speed can be achieved with at most 4 cells in isotropic non-totalistic rules with standard moore neighborhood - I think this has been proven for speeds of the form 1/m (m being any integer greater than or equal to 1 - 1c/m would technically also be right, where c is speed of light)

Also, is there a similar proof for diagonals of the form 1c/m

There is this problem that m can have infinite choices but there are only a finite number of isotropic non-totalistic rules with standard moore neighborhood. So the remaining work is to show that there are also a finite number of <=4 cell constellations to make it a spaceship in any such rules. I believe that the cells cannot be seperated too far apart, otherwise they will not interact or if they still interact it will be explosive (such as rules having a B1 or B2) and cannot form a spaceship. If this is true the conjecture is disproven since a finite number of spaceship choices cannot obtain an infinite number of orthogonal speeds.

I was thinking there might be an adjustable ship of some sort that would permit proof of this concept. I could be wrong and the low bound may be 5 cells, but I think whoever runs 5S may have some partial answer

Oh right, then your statement is very likely to be true. I believe there are certain rules (actually very easy to construct!) where such ships exists. For any orthogonal speed to be achieved though we might need one more cell to allow another integer distance as a piece information, since I don't think we have such brilliant rules where ships are adjustable with speed behaving according to Cantor's Matrix (that thing used to show that rationals have the same cardinal as naturals). Even with 5 cells there has to be very careful design of spaceships as the speed can be some near-half-c thing and the 3-cell ship is too slow processing rational speeds represented by the 2 single cells. One thing to clarify: does the ship itself has to be k-celled or it can be generated from a k-cell constellation? That could make a LOT of difference since explosive rules can literally create anything. I would then assume you mean the ship can be generated but the original k cells must not create anything other than the ship.

[NNlk05]

Conjecture: As n tends to infinity, there exists a upper bound of the max density still life smaller then nxn constructible by gliders that is less then the still life density cap 1/2.
Stronger conjecture: As n tends to infinity, there exists a upper bound of the max density pattern smaller then nxn constructible by gliders.

[vilc]

Conjecture: As n tends to infinity, there exists a upper bound of the max density still life smaller then nxn constructible by gliders that is less then the still life density cap 1/2.

Wrong, since arbitrarily large square patches of zebra stripes can be constructed.

[NNlk05]

Conjecture: As n tends to infinity, there exists a upper bound of the max density still life smaller then nxn constructible by gliders that is less then the still life density cap 1/2.

Wrong, since arbitrarily large square patches of zebra stripes can be constructed.

Huh. How?

[I6_I6]

Conjecture: As n tends to infinity, there exists a upper bound of the max density still life smaller then nxn constructible by gliders that is less then the still life density cap 1/2.

Wrong, since arbitrarily large square patches of zebra stripes can be constructed.

Huh. How?

Here's a 13x13 example:

Code: Select all

x = 15, y = 19, rule = LifeHistory
4.2A2.A2.A$4.2A2.4A$.A$.13C$.13DA$.13C$A13D$.13C$.13DA$.13C$A13D$.13C
$.13DA$.13C$A13D$.13C$13.A$3.4A2.2A$3.A2.A2.2A!

Edit: Never mind, I didn't know you meant glider constructible.

[vilc]

Huh. How?

You can use the method displayed in the long^N clock syntheses (see the continuous recipe). It would look like this, with a fast component to lay blocks on the ends :

Code: Select all

x = 49, y = 199, rule = B3/S23
32b2o$31bobo$31bobobo$32bobobo$34bobo$34b2o13$16bo3bo3bo3bo3b2o$12b2ob
obobobobobobobobobo$12b2obobobobobobobobobobobo$16bo3bo3bo3bo3bobobo$
34bobo$34b2o23$16b2ob2o3b2ob2o3b2o$12b2obobobobobobobobobobo$12b2obobo
bobobobobobobobobo$16bo3bo3bo3bo3bobobo$34bobo$34b2o16$15b2o3b2ob2o3b
2ob2o$15bobobobobobobobobobo$12b2obobobobobobobobobobo$12b2obobobobobo
bobobobobobo$16bo3bo3bo3bo3bobobo$34bobo$34b2o9$25bobo$26b2o$26bo2$37b
o$28bobo5bo$28b2o6b3o$29bo$26bo7bo$24bobo6bo$25b2o6b3o5bo$40bo6bo$40b
3o3bo$46b3o4$15b2o3b2ob2o3b2ob2o$15bobobobobobobobobobo$12b2obobobobob
obobobobobo$12b2obobobobobobobobobobobo$16bo3bo3bo3bo3bobobo$34bobo6b
3o$34b2o7bo$44bo22$16b2ob2o3b2ob2o3b2ob2o$15bobobobobobobobobobob2o$
15bobobobobobobobobobo$12b2obobobobobobobobobobo$12b2obobobobobobobobo
bobobo$16bo3bo3bo3bo3bobobo$34bobo$34b2o9$21bobo$21b2o$22bo2$11bo$12bo
5bobo$10b3o6b2o$19bo$14bo7bo$15bo6bobo$7bo5b3o6b2o$bo6bo$2bo3b3o$3o4$
16b2ob2o3b2ob2o3b2ob2o$15bobobobobobobobobobob2o$15bobobobobobobobobob
o$12b2obobobobobobobobobobo$12b2obobobobobobobobobobobo$3b3o10bo3bo3bo
3bo3bobobo$5bo28bobo$4bo29b2o17$16b2ob2o3b2ob2o3b2o$12b2obobobobobobob
obobobo$12b2obobobobobobobobobobob2o$15bobobobobobobobobobob2o$15bobob
obobobobobobobo$12b2obobobobobobobobobobo$12b2obobobobobobobobobobob2o
$15bobobobobobobobobobob2o$15bobobobobobobobobobo$12b2obobobobobobobob
obobo$12b2obobobobobobobobobobobo$16bo3bo3bo3bo3bobobo$34bobo$34b2o!