A Simpler Polynomial-Time Compilation to Cyclic Tag for Bounded Computation

Cyclic tag is a simple system which is universal, in that it can perform any computation. It is also a good target for showing other systems are universal. Proofs of its universality have either been simple but had an exponential size, including going straight through tag systems or through Fractran, or are especially complicated encodings such as one that goes through clockwise Turing machines. Here we show a system that is both more straightforward than the clockwise Turing machine method, and also more compact than any of those other methods. Our method goes through a path including some new systems we've come up with, cellular automaton or automata networks -> oblivious ring machines -> n-ary cyclic tag -> cyclic tag systems. One loses the ability to work with infinite tapes, however the substantial gains in efficiency could make the trade worthwhile for practical usage of this method, especially since computers that we can actually build are bounded in memory anyway. Cyclic tag and thus our system can be used in proving a number of other systems universal, and thus our system can be used for smaller finite constructions of such systems including finite rule 110 constructions, and additionally for Wolfram's especially small 2,3 Turing machine, it is possible that our system could be used to make that actual weakly universal proof of that system simpler and more efficient even on infinite tapes.