ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

3D, 4D or arbitrary multi-D gliders guns

For general discussion about Conway's Game of Life.

3D, 4D or arbitrary multi-D gliders guns

Postby Koiti Kimura » October 13th, 2017, 8:28 pm

Has anybody found such things? Has Professor Carter Bays discovered 3D guns? I'd like to know if high dimensional Lifes DID/DO turn out to be UTMs or not.
Koiti Kimura
 
Posts: 14
Joined: October 13th, 2017, 2:14 am

Re: 3D, 4D or arbitrary multi-D gliders guns

Postby Naszvadi » October 14th, 2017, 7:12 pm

Koiti Kimura wrote:Has anybody found such things? Has Professor Carter Bays discovered 3D guns? I'd like to know if high dimensional Lifes DID/DO turn out to be UTMs or not.


Hi,

No need for "artillery". All elementary one-dimensional cellular automata could be emulated on a six-dimensional euclydean grid using Neumann-neighbourhood and only 3 states. I constucted a subgrid-finder mixed integer linear programming model and solved with several open-source LP solvers. So there are simple rules in higher dimensions that support arbitrary computations due to Wolfram110.
Naszvadi
 
Posts: 192
Joined: May 7th, 2016, 8:53 am

Re: 3D, 4D or arbitrary multi-D gliders guns

Postby A for awesome » October 14th, 2017, 10:03 pm

Naszvadi wrote:So there are simple rules in higher dimensions that support arbitrary computations due to Wolfram110.

While you're allowing non-empty backgrounds, B6/S5678 in a cubical 3D Moore neighborhood can emulate CGOL in a two-cell-wide layer sandwiched (with a layer of empty space on each side) between one-cell-wide solid planes, and thus can do anything that Life can.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1440
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: 3D, 4D or arbitrary multi-D gliders guns

Postby dvgrn » October 14th, 2017, 10:49 pm

A for awesome wrote:
Naszvadi wrote:So there are simple rules in higher dimensions that support arbitrary computations due to Wolfram110.

While you're allowing non-empty backgrounds, B6/S5678 in a cubical 3D Moore neighborhood can emulate CGOL in a two-cell-wide layer sandwiched (with a layer of empty space on each side) between one-cell-wide solid planes, and thus can do anything that Life can.

Interesting -- I hadn't run into that additional "8" before. The old "Life 5766" that Carter Bays investigated seems to have been just B6/S567, and it also allows a six-cell-thick sandwich to emulate Conway's Life in the middle two layers.

If you hunt around, you can find papers from the 1990s about other gliders. Haven't noticed any 3D alien guns yet, though, except for the various trivial cases where a 3D rule emulates a 2D rule that has guns.

-- Those two links sure give a sense of the distance between 1990 computing technology and what's available today!
dvgrn
Moderator
 
Posts: 4022
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: 3D, 4D or arbitrary multi-D gliders guns

Postby calcyman » October 15th, 2017, 5:19 am

A for awesome wrote:
Naszvadi wrote:So there are simple rules in higher dimensions that support arbitrary computations due to Wolfram110.

While you're allowing non-empty backgrounds, B6/S5678 in a cubical 3D Moore neighborhood can emulate CGOL in a two-cell-wide layer sandwiched (with a layer of empty space on each side) between one-cell-wide solid planes, and thus can do anything that Life can.


I thought about similar things about 8 years ago, and realised that it's possible to make the 'bread' of the sandwich finitely-supported. In particular, take the rule:

B6/S45678

and sandwich a double-thick pattern between two blank layers and two layers of 'bread' resembling this:

x = 8, y = 12, rule = B6/S4678
b2o2b2o$8o$8o$b6o$b6o$8o$8o$b6o$b6o$8o$8o$b2o2b2o!


An 'open problem' I considered is whether it's possible for a two-cell-thick glider (which is a genuine glider) to escape from a sandwich into free space. If so, we can trivially port every CGoL glider gun into a B6/S45678 gun.

We can emulate six-cell-thick bilaterally-symmetric B6/S45678 patterns by means of an 8-state rule in the obvious way, and therefore run them in Golly.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1366
Joined: June 1st, 2009, 4:32 pm

Re: 3D, 4D or arbitrary multi-D gliders guns

Postby Macbi » October 15th, 2017, 5:46 am

What we would really want is some way to grow the bread at the edges, so that we can implement the unbounded Turing machine, and extend the universality of life to the new rule.
User avatar
Macbi
 
Posts: 170
Joined: March 29th, 2009, 4:58 am

Re: 3D, 4D or arbitrary multi-D gliders guns

Postby Gamedziner » October 15th, 2017, 6:51 am

For two-layer CGOL, you only need B6/S57.
Gamedziner
 
Posts: 386
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Re: 3D, 4D or arbitrary multi-D gliders guns

Postby Macbi » October 15th, 2017, 6:58 am

Gamedziner wrote:For two-layer CGOL, you only need B6/S57.

No, because then some live cells will appear outside your two layers and mess everything up.
User avatar
Macbi
 
Posts: 170
Joined: March 29th, 2009, 4:58 am

Re: 3D, 4D or arbitrary multi-D gliders guns

Postby Gamedziner » October 15th, 2017, 7:26 am

Macbi wrote:
Gamedziner wrote:For two-layer CGOL, you only need B6/S57.

No, because then some live cells will appear outside your two layers and mess everything up.

Good point. The glider still works, though.
Gamedziner
 
Posts: 386
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Re: 3D, 4D or arbitrary multi-D gliders guns

Postby Koiti Kimura » October 15th, 2017, 8:18 pm

How can you give a CA the three kinds of logic gates without guns, I wonder? Would anyone explain the principles outlines to me, a CA-ology beginner?
Koiti Kimura
 
Posts: 14
Joined: October 13th, 2017, 2:14 am


Return to General Discussion

Who is online

Users browsing this forum: No registered users and 3 guests