We study iterated transductions, where the basic transduc- tions are given by a class of length-preserving invertible transducers over the binary alphabet. It is shown that in some cases the resulting orbit relation is rational and we determine the complexity of several natural computational problems associated with the iterated transductions. 1 Iterating Transductions We are interested in the analysis of discrete structures of the form C = � C, T � where C is a rational set of words, in this context often referred to as the space of configurations ,a ndT is a functional binary relation on C determined by a rational transducer. While first-order properties of C such as reversibility or the existence of k-cycles are of considerable interest, higher order properties involv- ing T � ,t heiterate of T , are critical for the understanding of the structures. From a computational perspective, iteration of even rather simple transductions T produces structures C that are too complicated to admit a detailed analysis. To wit, the next-step function of a Turing machine is easily modeled as a ratio- nal transduction, so together with iteration we are dealing with a system that is potentially computationally universal and thus difficult to classify and under- stand. Perhaps the most surprising result along these lines is Cook's proof (3) of the universality of the elementary cellular automaton number 110, a transducer that is defined essentially by a ternary Boolean function. To the best of our knowledge, this is the first example of a universal system that was "discovered" rather than constructed, with the specific intent of producing universality. The argument relies heavily on a version of Post tag systems, so-called cyclic tag systems, and demonstrates that these systems, which are known to be com- putationally universal, can indeed be simulated by the transducer, given initial conditions of sufficient complexity. In fact, the argument employs bi-infinite bi- nary words to produce universality; more precisely, one needs to consider words of the form ω uwv ω where u, w and v are finite, binary words. This type of configuration is quite natural: letting C be the collection of all such words, the first-order structureC, Tis an elementary substructure of the full shift space � 2 Z ,Tof all bi-infinite words, where T is the transduction associated with the cellular automaton number 110, see (23). Remnants of this hardness result per- sist at the level of finite words, evaluation of the transduction on finite words is shown to be P-complete in (14).
['Klaus Sutner']
Invertible Transductions and Iteration