Is there any form that survives randomness? Detect and react

[Ben.F.Rayfield]

I am an artificial intelligence programmer (among other things) trying to build a shared space on the Internet where we would use intelligent tools to build more intelligent tools and visual interactive representations of thoughts, so we can see how our ideas fit together as a big puzzle in a high dimensional space. After searching for the basics of math and how intelligence works for years, I've found that those basics are inside Rule 110 (Turing Complete), Conways Game Of Life (Turing Complete, easy replicators, Hashlife), Rule 90 (for generating bell curves), and various statistical AI math that acts on bits, and this can all be represented in a grid of pixels being on or off. I want to create a space where we do something real on a large scale instead of Conway being just a game.

Are there forms which hold their shape while moving at any angle, and can change their angle if pushed by other objects, instead of the constant glider directions an brittle nature of most conway forms? Think soliton waves, bell curves, and that the fourier of a bell curve is another bell curve, which should happen naturally in conway because the sum of C^2 coins each as -1 or 1 is a bell curve of standard deviation C, and bell curves form circles, circles form waves, and here we are with the standard model of physics being some kind of automata. Its all computers in some form or another, some self reference and recursion. But back to the point... What conway forms can change their angle continuously like we do?

Are there forms which react the same way when their expected input, like a stream of gliders, arrives too early or late or in a modified form?

Can we build the logic of bayesian networks, boltzmann machines, and other statistical AI into a form in conway?

Can we build an intelligent life form that can survive randomness, think, and move through the game world?

The answer to all these questions, except the one about surviving randomness, is proven yes since conway is capable of general computing and as you can see in this video can reproduce its own behaviors (or modify them to some other logic of the 2d grid) http://www.youtube.com/watch?v=xP5-iIeKXE8

Given the highly optimized Hashlife which anyone can run Conways Game Of Life on, and that we can create new forms of hashlife using recursions of majority color and minority color (every on cell is 1 of 2 colors), it should be practical to build a real AI system inside the game, and hook it into other components so we can have a more fun and flowing view in a global network running such evolving forms.

[twinb7]

"...That can think and move through the game world?"

I've thought about this, because the existence of such a pattern would allow the most awesomely incredible evolution in Life ever.

However, after a long time thinking, my answer is no. With signals propagating at the speed of light even if there was a computer that could fix anything coming to it, the amount of time to get 'construction workers' there in time would be too great.

However, I've been wanting to make a CA rule that allows this kind of thing, so we'll see. I'll probably work on it over the weekend.

[Ben.F.Rayfield]

Then we change the speed of light by building some base component that only interacts with many copies of itself, maybe aligned on a grid, and define randomness as position of these components, not allowing any other forms on the board. Since conway is a general computer, all existing forms can be rebuilt in a way compatible with this. But we're going to have to solve this puzzle in some form. We cant keep building bigger and brittle forever.

[Andrew]

Are there forms which hold their shape while moving at any angle, and can change their angle if pushed by other objects, instead of the constant glider directions an brittle nature of most conway forms?

I doubt we'll ever see such patterns in Conway's Life, but SmoothLife seems to have what you want:
http://www.youtube.com/watch?v=KJe9H6qS82I

[dvgrn]

Are there forms which hold their shape while moving at any angle, and can change their angle if pushed by other objects, instead of the constant glider directions an brittle nature of most conway forms?

I doubt we'll ever see such patterns in Conway's Life, but SmoothLife seems to have what you want:
http://www.youtube.com/watch?v=KJe9H6qS82I

Depending on your definition of "pushed", it's certainly possible to set up self-replicating objects on a very tightly defined "supergrid" -- 2^20 cells on a side, let's say. At that point it becomes possible for a replicator that's traveling on the supergrid at (5,3) grid spaces per cycle to respond to the presence of a nearby replicator and travel at (5,2) instead. Or (5000,4999), or whatever.

Theoretically it's possible to do the engineering for that kind of thing in Conway's Life, but in practice it's not very interesting. It stretches Hashlife's abilities considerably to run even a single copy of the simplest self-replicating pattern. Getting all the way up to the next stability level, where a large number of such patterns are interacting on a Life supergrid, is not going to be within range of personal-computer power any time soon, I think.

It's kind of hard to get interested in solving all the detailed engineering problems with building a supergrid pattern if you can't really watch it run when you're done. Seems better to follow twinb7's line of thinking, and design a new CA that knocks a few orders of magnitude off of the lowest-level complexity.

Are there forms which react the same way when their expected input, like a stream of gliders, arrives too early or late or in a modified form?

Current replicator designs are made out of stable Herschel tracks, so they can certainly handle arbitrary variations in timing -- up to a point. It's possible to redesign them to handle spatial variation as well, but that would be kind of cheating -- every new glider lane or modification that you can handle would mean a huge increase in the size of the circuitry.

But that's the best we have at the moment; as you say, Conway's Life objects are incredibly brittle, pretty much without exception. Building an "intelligent Life form" in B3/S23 is pretty difficult when all you have to work with is barely-subcritical masses of enriched uranium... metaphorically speaking. There's no good way to handle mutations and randomness at the lowest level, because tiny changes cause disproportionately huge messes, which are then impossible to clean up because there's no way to build reliable sensors.

So all the randomness has to be in a Conway's Life supergrid, at the next level up -- and at that level we already don't have enough CPU power to do the simulation.

[Ben.F.Rayfield]

I am not looking for smoothlife because it may not be capable of general computing, like conway life has been proven to run a Turing Machine. It must be doable to run smoothlife on layers of conway life, but not necessarily the other way.

Interesting you call it uranium, because it was my research into the connection between the Clique problem of P vs NP, its connection to coin flips, bell curves, circles, waves, and then fermions vs bosons in a continuous field shaped as bell curves, which led me to the common parts between Conway Life and Go. P equals NP if any hashlife scales with Clique on the board, because 2^logBase2(p) = p, where hashlife is any hashcode algorithm and caching of p number of patterns in logBase2(p) cpu and memory cost.

If speed is a problem, I have some ideas for extremely improving the efficiency of hashlife, involving recursions of Majority Color and Minority Color (of which 3 cells create the color, of 2 possible colors, of each on cell) similar to how in the game Go a majority surrounding a minority captures that minority. If hashlife could handle more flexible patterns and much faster, is what I'm asking for doable?

[dvgrn]

If hashlife could handle more flexible patterns and much faster, is what I'm asking for doable?

I can certainly think of possible ways to increase the efficiency of the Hashlife algorithm for a few specific cases, like patterns with temporal or spacial periodicity that isn't a power of two. But special-case trickery won't be much help when the simulation problem is genuinely large and complex. I guess I'll believe "extreme improvements" to Hashlife when I see them.

If what you're asking for is "Can we build an intelligent life form that can survive randomness, think, and move through the game world?" -- well, theoretically possibly yes, but in practice it seems like that's still an unsolved problem even without the significant limitations of cellular automata.

Take Conway's Life as an example. At the lowest level it doesn't seem possible to design a life form that can even sense its immediate surroundings reliably -- the presence or absence of arbitrary still lifes nearby, for example. We can check for the presence or absence of any particular single object like a block, but if the block turns out to be a blinker we probably have an unexpected explosion on our hands.

With a great effort we might come up with a slow awkward test that handles either blinkers or blocks -- but then what about beehives, boats, beacons, barges, bakeries, or bi-blocks (to name just a few common possibilities)? Clearly hopeless. Put another way: I'd be reluctant to volunteer to design a super-clever environmental sensor usable by a Conway's Life form -- but I'd happily undertake to figure out how to break any such super-clever sensor if someone handed me one!

So a Life form in any elementary CA will likely have to be a higher-level structure under tightly controlled conditions -- a supergrid on top of the Life grid, running some kind of program. But emulation tends to be inefficient, often very inefficient. Might as well just code the higher-level system as efficiently as possible, and then when you've got your amazing moving intelligent Life forms working, you can say "we could simulate that in Conway's Life if we wanted to!"... and leave it at that.

[137ben]

In Reliable cellular automata with self-organization, Peter Gacs proved the existence of a 1-dimensional cellular automaton which is computationally universal, and for which a universal computer can survive random perturbation if the error rate is sufficiently small. It's pretty complicated (it has about 200 states per cell). There is also a simpler 2D UCA with the same property, although it is still pretty complicated. So, if we were not limited by hardware, a cellular automaton could support an error-resistant emulation of an artificial neural network that models a human brain...

I'm not sure if you could do it in B3/S23, though, because all known logic circuit components in life are very fragile.

[Gpennder_____409]

Then we change the speed of light by building some base component that only interacts with many copies of itself, maybe aligned on a grid, and define randomness as position of these components, not allowing any other forms on the board. Since conway is a general computer, all existing forms can be rebuilt in a way compatible with this. But we're going to have to solve this puzzle in some form. We cant keep building bigger and brittle forever.

no way can you change the speed of light 1, 2, it would have to be RANDOM STARTING PATTERNS:x.

[shouldsee]

A kinda relevant question: How difficult is it to emulate a simulation of a biological cell in cellular automata? And a neuronal network? Do I have to simulate a cell before I simulate a brain?

[Rich Holmes]

no way can you change the speed of light.

The speed of light is determined by the size of the neighborhood. Change the neighborhood, change c.

Of course, the size of the space of possible cell+neighbors configurations goes like, m^(n^2)? (m = # states, n = size of square neighborhood).

[shouldsee]

Since the definition of this form is "surviving" randomness, I figure it relevant to the evolution of a biological organism surviving randomness, which is amazingly elaborated in the following article on predictability of a biological evolution.

[shouldsee]

The discussion on B3/S23 (life like rule) is pretty complete, but I want to start another direction.

Based on the fact that dynamic ring survives under specific rule, there is possibility that they can detect environment and react.

One of the most trivial automata (see next reply) that supports ring is B3/S012V. If we allow 3 states the dynamic can be even more complex. v3k4_fish2 illustrate some other properties of rings but is not quite typical. I have collected some rules supporting rings under DDLab kcode notation but I don't have a script to translate them into golly rules. Another problem is some of these rules only work properly sequential/asynchronous updating, which is not supported by Golly natively.(It's a bit like turmite where you have an updating cell rasting through the cells and update them)

Code: Select all

x = 21, y = 24, rule = B13/S012V:T100,100
bobobobobobobobobobo$obobobobobobobobobobo$bobobobobobobobobobo$obobob
obobobobobobobo$bobobob3obobobobobo$obobob5obob3obobo$bobobo2b2ob2o2bo
bobo$obobob2obobobo2bobobo$bobob2obobobob2obobo$obo2bobobobobob2obobo$
bob4obobobobo4bo$obobo2bobobobo2b3obo$bobo2b3obobobobo2bo$obobo4bobobo
b4obo$bobobo2b3obob2obobo$obobob3o2bobo2bobobo$bobobobob2obo2bobobo$ob
obobobob5obobobo$bobobobobobobobobobo$obobobobobobobobobobo$bobobobobo
bobobobobo$obobobobobobobobobobo$bobobobobobobobobobo$obobobobobobob3o
bobo!

BTW, besides "Detect and react" ability, the capability for a ring to replicate itself is also very possible.

[Gamedziner]

The discussion on B3/S23 (life like rule) is pretty complete, but I want to start another direction.

Based on the fact that dynamic ring survives under specific rule, there is possibility that they can detect environment and react.

The most trivial automata that supports ring is B3/S012V. If we allow 3 states the dynamic can be even more complex. v3k4_fish2 illustrate some other properties of rings but is not quite typical. I have collected some rules supporting rings under DDLab kcode notation but I don't have a script to translate them into golly rules. Another problem is some of these rules only work properly sequential/asynchronous updating, which is not supported by Golly natively.(It's a bit like turmite where you have an updating cell rasting through the cells and update them)

Code: Select all

x = 21, y = 24, rule = B13/S012V:T100,100
bobobobobobobobobobo$obobobobobobobobobobo$bobobobobobobobobobo$obobob
obobobobobobobo$bobobob3obobobobobo$obobob5obob3obobo$bobobo2b2ob2o2bo
bobo$obobob2obobobo2bobobo$bobob2obobobob2obobo$obo2bobobobobob2obobo$
bob4obobobobo4bo$obobo2bobobobo2b3obo$bobo2b3obobobobo2bo$obobo4bobobo
b4obo$bobobo2b3obob2obobo$obobob3o2bobo2bobobo$bobobobob2obo2bobobo$ob
obobobob5obobobo$bobobobobobobobobobo$obobobobobobobobobobo$bobobobobo
bobobobobo$obobobobobobobobobobo$bobobobobobobobobobo$obobobobobobob3o
bobo!

BTW, besides "Detect and react" ability, the capability for a ring to replicate itself is also very possible.

Code: Select all

x = 1, y = 1, rule = B78/S0
o!

Trivial.



P.S.:I think this topic now belongs in Other Cellular Automata.

[shouldsee]

Code: Select all

x = 1, y = 1, rule = B78/S0
o!

Trivial.



P.S.:I think this topic now belongs in Other Cellular Automata.

You are right that my wording wasn't precise enough.

But I still don't see how this pattern you posted is trivial for a ring? You sure this is the correct pattern?

Since it's a conceptual idea, I am not sure which forum section is the best.

[Gamedziner]

Code: Select all

x = 1, y = 1, rule = B78/S0
o!

Trivial.



P.S.:I think this topic now belongs in Other Cellular Automata.

You are right that my wording wasn't precise enough.

But I still don't see how this pattern you posted is trivial for a ring? You sure this is the correct pattern?

Since it's a conceptual idea, I am not sure which forum section is the best.

The pattern will survive any randomness. Any survival conditions containing S0 will work, as long as the only birth requirements are B0, B7, and/or B8 (only talking about totalistic rules here).

Some examples to prove my point:

Code: Select all

x = 3, y = 3, rule = B78/S012345678
3o$2bo$obo!

Code: Select all

x = 3, y = 3, rule = B78/S01345678
b2o$2bo$obo!

Code: Select all

x = 3, y = 3, rule = B78/S012345678
2bo$2bo$obo!

Code: Select all

x = 3, y = 2, rule = B78/S012345678
2bo$obo!

Code: Select all

x = 3, y = 1, rule = B78/S01345678
obo!

Even more trivial is the case of B/S012345678, since nothing reacts. Ever.

[shouldsee]

Even more trivial is the case of B/S012345678, since nothing reacts. Ever.

Okay I got your point now. The problem with trivial examples are being not dynamic. S012345678 prohibits state0 to take over any state1 cell. Nevertheless, survival of the state0 becomes the new problem.

[Gamedziner]

Even more trivial is the case of B/S012345678, since nothing reacts. Ever.

Okay I got your point now. The problem with trivial examples are being not dynamic. S012345678 prohibits state0 to take over any state1 cell. Nevertheless, survival of the state0 becomes the new problem.

I did not specify any birth rules, either. Therefore, state0 will not be taken over by any state1 cell, either.

Yeah, trivial examples are not dynamic.