A095950 Number of distinct excluded blocks of length n in the evolution language of width 1 (i.e., time series) generated by the elementary cellular automaton of Rule 110, which has the capability of a universal Turing machine.

1, 3, 3, 5, 6, 12, 16, 17, 38, 42, 73, 112, 198

Offset

5,2

References

Zhi-Song Jiang, Hui-Min Xie, Evolution Complexity of the Elementary Cellular Automaton Rule 18, Complex Systems, 13 (2002) 271-195

Stephen Wolfram, Computation theory of cellular automata, Commun. Math. Phys. 96 (1984) 15-57

Huimin Xie, Grammatical Complexity and One-Dimensional Dynamical Systems, World Scientific, Singapore, 1996

Links

Table of n, a(n) for n=5..17.

Example

For length 5 binary blocks, only one block, 11101, cannot be found in the time series generated by the elementary cellular automaton of Rule 110.

Crossrefs

Sequence in context: A183561 A300183 A222704 * A089874 A092035 A164914

Adjacent sequences: A095947 A095948 A095949 * A095951 A095952 A095953

Keyword

nonn

Author

Huimin Xie (szhmxie(AT)pub.sz.jsinfo.net), Jul 13 2004

Status

approved