And having done this, the next stage is to get such a tag system to emulate a Turing machine. The pictures on the next page illustrate how this can be done. But at least with the particular construction shown, the resulting Turing machine can only have cells with two possible colors. The second set of pictures below demonstrate, however, that such a Turing

A cyclic tag system emulating a tag system that depends only on the first element at each step. In the expanded tag system evolution, successive colors of elements are encoded by having a black cell at successive positions inside a fixed block of white cells.

Turing machines with two colors emulating ones with more colors.

Exportable Images for This Page:

From Stephen Wolfram: A New Kind of Science [citation]