40mins de préférence

Joint work with: Daria Pchelina (LIPN), Shinnosuke Seki (UEC Tokyo), Guillaume Theyssier (I2M)

Oritatami systems are a model of molecular co-transcriptional folding: the transcript (the “molecule”) folds as it is synthesized according to a local energy optimisation process, in a similar way to how actual biomolecules such as RNA fold into complex shapes and functions while being synthesized (transcribed).
We introduce a new model, called \emph{turedo}, which is a self-avoiding Turing machine on the plane that evolves by marking visited positions and that can only move to unmarked positions, hence growing a self-avoiding path.
Any oritatami can be seen as a particular turedo.
We show that any turedo with lookup radius 1 can conversely be simulated by an oritatami, using a universal bead type set.
Our notion of simulation is strong enough to preserve the geometrical and dynamical features of these models up to a constant spatio-temporal rescaling (as in intrinsic simulation).
As a consequence, turedo can be used to build readily oritatami ``smart robots'', using our explicit simulation result as a compiler. Furthermore, as our gadgets are simple enough, this might open the way to a readable oritatami programming, and these ingredients could be regarded as a promising direction to implement computation in co-transcribed RNA nanostructures in wetlab.

As an application of our simulation result, we prove two new complexity results on the (infinite) limit configurations of oritatami systems (and radius-1 turedos), assembled from a finite seed configuration.
First, we show that such limit configurations can embed any recursively enumerable set, and are thus exactly as complex as aTAM limit configurations.
Second, we characterize the possible densities of occupied positions in such limit configurations: they are exactly the $\Pi_2$-computable numbers between 0 and 1.
We also show that all such limit densities can be produced by one single oritatami system, just by changing the finite seed configuration.

None of these results is implied by previous constructions of oritatami embedding tag systems or 1D cellular automata, which produce only computable limit configurations with constrained density.

Note that, reframing our results, we prove that doodling without lifting the pen nor intersecting lines and using only a 1-local view to decide for the drawing directions produce drawings as complex and as dense as can be.