Complex Systems -> Universality in Rule 110 -> Matthew Cook

From: Genaro Juárez Martínez (genarojm_at_correo.unam.mx)
Date: 12/17/04 

Date: Fri, 17 Dec 2004 14:58:08 +0000 (UTC)

Finally the demonstration that Rule 110 is universal made by Matthew
Cook and presented in a conference at the Santa Fe Institute in 1998,
has been published in Complex Systems.

\bibitem{kn:Cook04} Matthew Cook, ``Universality in Elementary Cellular
Automata,'' {\em Complex Systems}, Volume 15, Number 1, pp. 1-40, 2004.

We shall give a small revision and general commentaries with regard of
this result.

Universality in Rule 110 provides important results both in computation
and cellular automata theory.

Thus there is a Turing machine that emulates the behavior of Rule 110
(apparently developed by David Eppstein), the formulation of the cyclic
tag systems and its construction in Rule 110.

1. New cyclic tag machines

Cook offers a demonstration using tag systems taking as basis the
results of Cocke-Minsky (1964), and extending them to cyclic tag
systems.

Cyclic tag systems and their universality are originally developed by
Cook. This way the cyclic tag systems are interesting by their own right
because they represent a new mechanism to realize computations,
therefore they must be independently analyzed.

We can see some antecedents in circular machines by Arbib (1969), and
the universal circular Post machines by Kudlek-Rogozhin (2001).

A pair of productions is propose (N -> $, Y -> YY) and (N -> $, Y ->
YN) where $ represents the empty word. Then depending on the initial
value in the tape, the production system must be aligned in the
evolution space of Rule 110.

The system starts with a Y in the tape, and the problem of determining
if this machine has a periodic behavior or disappear, is undecidable.
Analogously to the results by Post (1936) there are several an
interesting open questions:

Can we demonstrate if the problem is undecidable or partially
undecidable?, or intractable?

The cyclic tag systems can find a solution to all problems for u, and v
>= 3?.

Cook 's machine belongs to some of universal circular Post machines of
Rogozhin?.

2. Construction in Rule 110

In a similar way that Life, the construction is based on collisions
among gliders. In this particular case, periodic blocks of gliders work
both as operators and data.

This construction is very impressive and also very sensitive to initial
conditions. It has three important parts in the evolution space of Rule
110.

a) Periodic blocks arriving from the left.

These blocks are formed by packages of A^4 gliders representing
operators, they must transform the periodic blocks arriving from the
right. The transformed values represent data in the tape of the cyclic
tag system.

The distances in each package of gliders are doubled or tripled with
regard of the blocks coming from the right, in order to get a correct
operation.

b) Data in the tape.

The initial datum is restricted to initiate with Y in the Cook's system.
Data are represented by blocks of C2 gliders (four gliders in different
phases). The difference between the data representing Y or N is the
distance between the two internal C2 gliders of each block.

Each data in the tape is erased by a leader (block of E and E- gliders).

c) Periodic blocks arriving from the right.

They represent two important parts. In the initial condition they are
blocks (of E- gliders) without transforming. When the leader finds a Y
in the tape, the blocks without transforming are firstly transformed
into groups of four E- gliders. In the opposite case all the blocks are
erased until finding the following leader.

-----------------------

If you wish to find Cook's paper by Google (or another tool in Internet)
using key words like: universality cellular automata, Rule 110, cyclic
tag systems, Matthew Cook Rule 110, etc.

Peculiarly no search will lead you at Cook's paper in Complex Systems !

-genaro 

-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
Quantcast