Transducers with Programmable Input by DNA Self-assembly.

Notions of Wang tiles, finite state machines and recursive functions are tied together. We show that there is a natural way to simulate finite state machines with output (transducers) with Wang tiles and we show that recursive (computable) functions can be obtained as composition of transducers through employing Wang tiles. We also show how a programmable transducer can be self-assembled using TX DNA molecules simulating Wang tiles and a linear array of DNA PX-JX 2 nanodevices.