[FOM] message of Genaro for FOM

[genarojm@correo.unam.mx]

Subject: Present state in small Turing machines

There is a remarkable set of advances in computation theory, in particular
related with other areas.

For example in cellular automata theory,  John von Neumann developed in 1945 an
important progress on demonstrating that a small cellular automaton small is
universal ! There is a reference containing interesting questions in computation
theory:

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

Cellular automata are discrete dynamic systems which evolve in one or several
dimensions.

Von Neumann (Cood 1966) shown universality with an automaton of two dimensions
handling 29 elements as a set of states and with a function evaluating 5
elements in the space.

Other famous automaton was developed by John Horton Conway (1970) and it has
been proved its universality  by means of simulating a register machine  (1982).
This is  an automaton of two dimensions with 2 elements in the set of states and
with a function that evaluates 9 elements in the space.

Cook (1998) demonstrated that a one-dimensional automaton with 2 elements in the
set of states and with a function that evaluates 3 elements in the space is
universal !!. The automaton is called "Rule 110" because of the binary

representation of the function in decimal notation is : 110 = (01110110)_2

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 system and its construction in Rule 110.

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

This way the cyclic tag systems are interesting by their own right because
theyrepresent a new mechanism to realize computations, therefore they must be
independently analyzed.

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

A pair of productions is propose in cyclic tag system (0 -> $, 1 -> 11) and  (0
-> $, 1 -> 10) 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 1 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?

Which is the difference between a undecidable and intractable problem?

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

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

Is there a secuence of unsolvable->intractable->undecidable problems?

Which is the present state of small Turing machines?

-genaro


-------------------------------------------------
www.correo.unam.mx
UNAMonos Comunicándonos