Showing Text From Page 669 | View full page with images

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

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

Turing machines with two colors emulating ones with more colors.

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