[How to find a "useful" CA ?] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


How to find a "useful" CA ?

(Click here to view the original thread with full colors/images)


Posted by: janos

The NKS book mentions a few CAs who are doing "usefull" calculations, like adding two numbers to each other, etc..

It looks to me that the discovery of it was "post-CA", that is first the CA was looked at, and in a moment the "aha" discovery was made that by the way it adds two numbers together.

Is it possible to do the reverse ?

Let say I am looking a number N and I would like to craft a CA which would provide all the {P,Q} numbers that P+Q=N and P and Q are Primes. For example for N=10, I would have P and Q as {3,7} and {5,5}

Where should I start ?


Posted by: Brian Prentice

To develop a CA to perform a specific task, simply write a program to implement certain primitive behavior such as cell movement and cell interaction. Then arrange groups of cells into patterns giving each cell member an initial state. Two example CA's that implement logic gates are here:

http://linuxenvy.com/bprentice/MCel...icleStreams.zip

To run these CA's you will need the current version of MCell which is here:

http://www.mirekw.com/ca/index.html

and you will need to extend MCell by installing the DLL's that are included in the zip achieve. The Delphi source code is also included.

A more interesting question is: Can a CA evolve to perform such tasks without being specifically programmed to do so?

Brian Prentice


Posted by: Richard J. Gaylord

"To develop a CA to perform a specific task, simply write a program to implement certain primitive behavior such as cell movement and cell interaction."

this is, to my view, an totally wrong-headed approach which contradicts the whole idea of using simple programs to give rise to complex behavior.

eg., try to develop a CA to move a glider across space using rules you develop specifically for glider motion (in other words, you can NOT use the rules of the game of life because those rules do not explicitly involve cell movement of glider objects. the rules you will come up with will be much more complicated than the rules of the game of life and moreover, they will only describe glider motion and not the myriad other life-forms and their behaviors observed in ther game of life. so, if you then continue by looking at the catalog of life-forms and their behaviors with other life-forms and writing a set of rules for each one, you will have an incredibly large number of rules and i would guess that from this immense collection of rules, you will never deduce the underlying 3 rules [more-or-less depending on how you write them] that are the FUNDAMENTAL rules of the game of life. and of course, the amazing beauty of the game of life will be lost entirely.

one the major deficiencies in current theoretical physics is that it tries to do precisely what is suggested - it looks at a phenomenon and then tries to write the equations to describe that phenomenon based on the entities it 'observes'.

the game of life should serve as the exemplar of stephen's idea [sorry, i know he didn't create it - and i'll never understand how john conway came up with it, unless it was by pure luck].


Posted by: Brian Prentice

Richard,

You have criticized my answer to Janos's question without answering it yourself. I would enjoy reading your answers to both Janos's original question and to the broader question that I asked.


Posted by: Richard J. Gaylord

"A more interesting question is: Can a CA evolve to perform such tasks without being specifically programmed to do so?"

i am also not sure what you mean by having a CA evolve. do you mean that the properties of the CA evolve while the rules remain the same or that the rules of the CA evolve?

either way, this is a very deep question. it brings us to the foundations of evolution.

note: people in kansas might not want to continue reading this as it might offend their fundamentalist sensibilities.

i am personally more interested in the evolution of rules of behavior rather than the evolution of behavior itself - though i think this is in some way, antithetical to the wolfram approach

note: the above statement may seem to be in conflict with my previous posting but as walt whitman said "Do I contradict myself? Very well, then I contradict myself, I am large, I contain multitudes."

anyway, there are various approaches to evolutionary programming but they all seem to require the use of some criterion of 'fitness' which is imposed externally [i suppose that one could say that in the natural world, survival is the externally imposed requirement for evolution, though i have always felt that the phrase 'survival of the fittest' is a misunderstanding of darwinian thought and should be replaced by 'elimination of the least fit'].

if a CA were not programmed specifically to perform a task or programmed in such a way as to 'encourage' the CA to develop the ability to perform the task then if by luck, it developed the ability to perform the task, it would be likely to continue to evolve and could well lose that abiility, unless of course you monitor the system and tell it to stop evolving once it can perform the task (a run-on sentence if ever ijj've read one). i should note that this actually happens in the natural world where capabiities develop and then go away.

which brings us to the question of whether mathematics evolves as nature evolves. that's a really heavy topic and is actually relevant to wolfram science.

i would like to hear other people's ideas on this.


Posted by: janos

Let me re-phrase the question, because I see that the discussion above "wonders off the trail" :)

Here is a simple program in Mathematica to calculate for a given 'n' the available pairs of primes whose sum is 'n'. I am doing for n=10.

In[32]:=
n = 10;
aa = First[Last[Reap[
p = 1; While[p <= n/2,
Which[PrimeQ[p] &&
PrimeQ[n - p],
Sow[{p, n - p}]];
p++; ]]]]
Out[33]=
{{3, 7}, {5, 5}}

I am looking for a CA where I can specify a rule - or combination of rules -, initial condition which might depend on 'n' and the number of steps which again might depend on 'n' and after the CA ran its course, I could see that let's say on the bottom row there would be from the left 3 black cells followed by 7 white cells, then some kind of divider and then 5 black cells followed by 5 white cells.
Or, if it is not on the bottowm row, but in the "center column" that is even better :)

So the question is, if I know ahead, what kind of computation do I want to do, how one can embark to craft a CA which does the requested computation. I know it is somewhat counter-intuitive to the promise of NKS that you must search the computational universe to find or fall over on the solution, but as I am reading Penrose at bedtime, I would like to see if CAs can perform in Old Kind of Science as well.

If I have to search the computational universe for the CA, then the question is what kind of search should I employ to find it as I am varying rules, initial conditions and steps ? Or, if it is easier to emulate let's say with a tag system, then how should I search for such a tag system.

Thanks ahead,

J‡nos


Posted by: Jason Cawley

There is a group lead by Johan Veerman that has investigated this, e.g. by doing searches to find CAs that compute various simple mathematical functions - addition, multiplication, powers e.g. His summer program bio is here -

http://www.wolframscience.com/summe...ts/veerman.html

An entirely different approach is to take some known universal system and encode the calculation. That is straightforward but results in some highly elaborate initial passed to an entirely general rule, with no thought of simplicity or efficiency. It is akin to writing a "compiler" for that rule, or to make it simpler, for a limited problem addressed by that rule. This is a sort of OKS computer science way of noticing that it is possible.

Personally I think Veerman's approach is the more interesting one, certainly more NKS. How do you start doing it? Pick a base or encoding, unary e.g. Search for rules doing anything remotely like what you need (binary counting you find right away. Multiplication isn't too hard, using particle "passes" across some structure to "count". Etc). You find something that doesn't quite, but has useful particles that might perform the computations when assembled. Then you can tinker with them, e.g. by adding extra states to let them pass through each other where they don't "naturally" ("color 3 behaves just like 1 except..."), and the like.

The approach he has taken is to start with calculations that CAs readily do, in ways that are obvious or noticable. And then to look for slightly harder ones. So he is not starting with some calculation meant to be difficult, he is picking off the "low hanging fruit" first. With the eventual idea, though, of building up a "stable" of identified CAs that do "useful" things. I hope this helps. I'm sure Veerman could tell you more than I could about getting it to work.


Posted by: Johan Veerman

What we have been trying to do is to find CAs that perform arithmetical calculations. There are two basic ways to do this: by specifically constructing them to do a certain task (e.g. addition, subtraction, etc.) and by doing searches in a CA rule space.

For both cases, you first have to work out a way of encoding / decoding the input / output. For our case, we consider a unary base. For example, say you want to add 2+3, then the initial condition is given by: 112111, where the ones are the input and 2 is the particle that will start moving around to perform the calculation. This is only one type of encoding.

For the first case (specific construction), we start with doing arithmetical calculations in a serial way, that is, a particle first moves to read one of the inputs and then adds (or whatever mathematical function you are using) it to the other one. Even though the rule you find ends up with a lot of states, depending on the type of operation you want it to perform, and it is not simple anymore, you end up with a certain feeling of what different types of behavior you need. We then move on to construct CA rules that perform the same tasks but in a parallel way, therefore with a fewer number of states and steps.

For the second method (searching in a rule space), at first we did some exhaustive searches, but if you want a CA to perform, say multiplication, you would need to search in a space with at least 5 colors, which gives you 5^125 rules. Since this an impossible task, we put some restrictions that we found with the specific constructions and add some appropiate filters (e.g. halting condition) in order to do a more directed search.

This is a quick overview of how we have been doing this. As Jason has already pointed out, the best approach is to first start with some basic behavior, and then move on to a more complicated task. We have also some extensions of this work (extending the radius, using other bases) as well as CAs that perform bitwise logical operations and even sorting. I will try to put them in a single notebook and then post it later on.




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings