[rule110] impossible strings on cellular automata

In the note on Cellular Automata we discussed a class of simple linear 
two-state automata in which each field value ft+1(j) is either 0 or 1, 
and is a fixed function of the three prior values ft(j-1), ft(j), and 
ft(j+1). We saw how the 256 distinct functions ("rules") of this type 
can be placed into 88 equivalence classes up to direction reversal and 
field value complementation. Furthermore, we noted that for any given 
rule there may be impossible (excluded) strings, i.e., strings that are 
not the successor of any string. For any given rule, we can list the 
total number of k-bit excluded strings for k = 1, 2, ... etc. This 
gives sequences of integers, and we found that there are only 31 
distinct sequences. The members of each of the 88 equivalence classes 
of rules fall into one of these 31 "exclusion classes". The largest 
single exclusion class consists of the rules that do not exclude any 
strings. At the other extreme, Rule 0 excludes all but one string. In 
between these two extremes are the other 29 exclusion classes, with 
varying degrees of exclusivity.....

for a complete information...

http://www.mathpages.com/home/kmath421/kmath421.htm


-abdiel caceres gonzalez
====================
Centro de Investigacion y de Estudios Avanzados IPN
Mexico DF
http://computacion.cs.cinvestav.mx/~acaceres
tel.[01|044] 55-1171-4008


---------------------------------------------------------------------------
list archives  : http://www.freelists.org/archives/rule110
change options : http://www.rule110.org/contact.html
or sign off by mailing to list-request@xxxxxxxxxxx - subject: 'unsubscribe'

Other related posts: