[2017 MPRI 2.11.1] Molecular programming 2/4 (25 OCT)

COURSE MPRI 2.11.1 - Molecular Programming
Lecture 2/4: Universality in tile assembly systems
By: Nicolas SCHABANEL, CNRS (IRIF, U. Paris Diderot)
Parisian Master of Computer Science (MPRI)

[0:00:00] Simulating Turing Machines at T°=2
[0:29:02] Kolmogorov Complexity
[0:54:16] Lower Bounding the minimal number of tiles to hardcode the input seed with Kolmogorov C.
[1:06:43] Optimal number of tiles for harcoding the seed
[1:42:54] Exercise session: Assembly time = O(rank) w.h.p.