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
