Re: Reversal of Conway's Life Algorithm


Subject: Re: Reversal of Conway's Life Algorithm
From: Dathan (dathan_bennett@yahoo.com)
Date: Tue Jan 11 2000 - 02:15:17 MET


dale <djohnson@v-wave.com> wrote in message
news:DSge4.16651$G55.224576@news1.rdc1.ab.home.com...
> >
> > Actually, I'm only planning on running it back a few iterations, so size
> of
> > the search tree wouldn't be too much of a problem, or shouldn't be.
After
> > all, I could just divide a large grid into a bunch of smaller ones for
the
> > original search. The code to decide that the values of a certain area's
> > squares is unaffected by the values of far-off squares should be fairly
> > simple to write.
> >
>
> if your grid is 4 x 4, and at time T, your grid should be 6 x 6 at time
> T-1, 8 x 8 at time T-2, and 10 x 10 at time T-3 in order to eliminate
> border effects. your tree would have the 4 x 4 matrix as its root,
> then branch to "n" 6 x 6 trees. To figure out time T-1, you more
> or less have to search through 2^(6x6), 68 trillion possible boards
> which may have produced the 4 x 4 board of interest. when you
> locate those boards (perhaps 20 or 30), they are the next level
> of your tree. you then have to search through 2^(8x8),
> 10^19 possible 8 x 8 boards which may have produced
> your 6 x 6 boards, and compare against the 20 or 30 in
> your previous set. This may be larger, there may be 100 or so
> per branch, forming the third level of the tree.
>
> that is the brute force method. if you know more about what you're
> looking for maybe there are shortcuts. keep posting!
>
> Dale.
>
>

I started thinking about the brute force method after I posted, and realized
that I was mistaken, especially after I read your post and saw just how
outrageous the numbers are (I didn't do any real math in my pondering).
Instead, I was thinking of maybe storing a database with either figures in
it or some sort of coded description of figure behavior. Then, a
(sophisticated) pattern-matching algorithm could be applied to yield a
starting point for the reverse-engineering process, since I don't think I
am, at this time, near ready to write a comprehensive pattern-matching
algorithm. I could write one that would start at a "best guess" population
layout and modify squares on the grid that it would tag as "critical" until
it stumbled upon the right one. However, I would probably be better off
just starting a new science fair project at that point, because such an
implementation would be almost useless to my purposes. Perhaps I _should_
get a new project, but this one just intrigues me a lot. If anyone stumbles
across any information on the subject, _please_ post it here or mail it to
me.

Dathan

############################################################################
This message was posted through the fuzzy mailing list.
(1) To subscribe to this mailing list, send a message body of
"SUB FUZZY-MAIL myFirstName mySurname" to listproc@dbai.tuwien.ac.at
(2) To unsubscribe from this mailing list, send a message body of
"UNSUB FUZZY-MAIL" or "UNSUB FUZZY-MAIL yoursubscription@email.address.com"
to listproc@dbai.tuwien.ac.at
(3) To reach the human who maintains the list, send mail to
fuzzy-owner@dbai.tuwien.ac.at
(4) WWW access and other information on Fuzzy Sets and Logic see
http://www.dbai.tuwien.ac.at/ftp/mlowner/fuzzy-mail.info
(5) WWW archive: http://www.dbai.tuwien.ac.at/marchives/fuzzy-mail/index.html



This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 15:59:37 MET DST