I think I have found new intersting CA-like formula

[Diagoras]

Hello, all.

I need your help in understanding if I have found something new or it is allready known thing. Generic formula for this 2d-something is pretty simple:

s(2t,x,y) = δ( s(2t-1,x,y) , s(2t,x-1,y) , s(2t,x,y-1) )
s(2t+1,x,y) = δ( s(2t,x,y) , s(2t+1,x+1,y) , s(2t+1,x,y+1) )

where s(t,x,y) is state of cell at (x,y)-coordinates in t moment of time and δ(S0,Sx,Sy)->S1 is some state-transition function. With carefully designed state-transition function this formula produces very interesting regular and fractal patterns even for only 3 possible states. Please tell me if you have seen something like this before. If no, I can post some screenshots of its evolution and even java-driven alpha implementation for your enjoyment.

Thank you in advance.

[ebcube]

Sounds interesting. Post the screenshots and the implementation ^^

[Diagoras]

This is selected screenshots of one evolution in 400x400 field starting from random pattern (3 states - Red, Green and Blue):






Implementation will follow tomorrow.

[calcyman]

s(2t,x,y) = δ( s(2t-1,x,y) , s(2t,x-1,y) , s(2t,x,y-1) )
s(2t+1,x,y) = δ( s(2t,x,y) , s(2t+1,x+1,y) , s(2t+1,x,y+1) )

Unfortunately, that's not a cellular automaton, as each generation should depend only on previous generations, not on other cells in the current generation. In fact, on an infinite grid, your system cannot be simulated by a Turing machine, as it can be made to solve the Halting Problem in two generations.


As a matter of interest, why did you use delta as the transition function? At first glance, it tricked me into thinking that I was looking at a partial differential equation.

[Keiji]

In fact, on an infinite grid, your system cannot be simulated by a Turing machine, as it can be made to solve the Halting Problem in two generations.

How did you figure that out?

[calcyman]

How did you figure that out?

If you look at the recurrence relation, in even generations, a cell is affected by its previous state, and the current states of the cell above and to the left of it:

Code: Select all

......
......
...o..
..o*..
......
......

Since the cell marked * is affected by both cells marked o, it simulates a two-neighbour one-dimensional cellular automaton -- in just one generation.

A two-neighbour one-dimensional cellular automaton can be made to emulate any one-dimensional cellular automaton, including a cellular automaton corresponding to a Turing machine on a tape.

The CA can be engineered so that the Turing machine, when halting, turns that cell to a specific state.

In the next generation, the neighbourhood is reversed:

Code: Select all

......
......
..*o..
..o...
......
......

Now, information can propagate at infinite speed in the opposite direction, and the fact that the Turing machine has halted can be relayed back to the initial cell.

So, you won't be able to make a program to simulate (an arbitrary transition rule) on infinite grids, since I could engineer it to determine whether there are any Fermat primes above 65537 in just two generations.

[Diagoras]

Unfortunately, that's not a cellular automaton, as each generation should depend only on previous generations, not on other cells in the current generation. In fact, on an infinite grid, your system cannot be simulated by a Turing machine

Yes, I do know, because of this I'm not calling it "cellular automaton", but "CA-like something"

As a matter of interest, why did you use delta as the transition function? At first glance, it tricked me into thinking that I was looking at a partial differential equation.

Sorry, no meaning behind that - just random letter. May be it came from my days of playing with state machines or something.

Here I posted java version from which I get earlier screenshots:
https://docs.google.com/leaf?id=0B6YgyK ... y=CJDuoJ8K

It is extremly simple. It just fills 400x400 field with random pattern and you can press "Space" for one step. Sources will follow a little later.

[ebcube]

I can't open nor download it. 404

[Diagoras]

Damn google. Looks like it is paranoid about trojans. Anyone knows, where can I host small archive with ".jar" inside without registration? I see no attach file function on this board

[Diagoras]

Damn google. Looks like it is paranoid about trojans. Anyone knows, where can I host small archive with ".jar" inside without registration? I see no attach file function on this board

[ebcube]

Use Mediafire: http://mediafire.com

[calcyman]

I see no attach file function on this board

You can attach any ZIP to this board using the 'Upload attachment' tab.

[Diagoras]

You can attach any ZIP to this board using the 'Upload attachment' tab.

My fault, sorry. Attaching now.

[Keiji]

Could not find the main class: cellauto.CellAutoApp. Program will exit.

[Wojowu]

I have the same thing

EDIT:
To make it work, you must un-zip files