After a translation of an input string, x, to an output string, y, a self-reproducing pushdown transducer can make a self-reproducing step during which it moves y to its input tape and translates it again. In this self-reproducing way, it can repeat the translation n-times for any n ≥ 1. This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self-reproducing pushdown transducer that repeats its translation no more than three times.
['Alexander Meduna', 'Lubos Lorenc']
Self-reproducing pushdown transducers.