[2016 MPRI 2.11.1] 7. Nature Programming: Intrisic Universality & Other models including Oritatami (2016/11/9)

MPRI - Parisian Master of Research in Computer Science
Course 2.11.1: Approximation Algorithms, Randomization & Nature Programming
Nicolas SCHABANEL, CNRS - Université Paris Diderot

LECTURE 7 (2016/11/9)
NATURE PROGRAMMING: INTRINSIC UNIVERSALITY & OTHER MODELS INCLUDING ORITATAMI

[0:00:00] 0. Theory vs Practice
[0:04:59] 1. Intrinsic Universality of Tile Assembly Systems at T°=2
[0:39:20] 2. One (Polygonal) Tile is Enough!
[0:43:00] 3. Other Models: Bio-Logical Circuits
[0:49:43] 4. Nubots: a Model for Molecular Reconfiguration
[0:54:07] 5. About Experiments: Nanotubes that Compute
[0:58:26] 6. Oritatatami: one Molecule that computes co-transcriptionally
[0:58:54] 6.1 Experiment: Synthetic RNA Co-Transcriptional Folding-based Meshes
[1:11:58] 6.2 Oritatami: A Model for Co-Transcriptional Folding
[1:18:02] 6.3 Oritatami: How to Compute?
[1:31:55] 6.4 Oritatami: Rule Design is NP-hard but Fixed Parameter Tractable
[1:41:20] 6.5 Oritatami Systems simulate efficiently Turing machines
[2:04:36] 6.6 Oritatami: How to Prove the Correctness?
[2:28:48] 6.7 Oritatami: Conclusion