[2016 MPRI 2.11.1] 6. Nature Programming: Universality in Tile Assembly Systems (2016/11/2)

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

LECTURE 6 (2016/11/2)
NATURE PROGRAMMING: UNIVERSALITY IN TILE ASSEMBLY SYSTEMS

[0:00:00] 0. HW4: NP-completeness & Optimization Problems
[0:05:43] 1. Turing Universality in tile assembly systems
[0:12:31] 2. Turing universality at T°=2
[0:36:19] 3. Turing universality at T°=1
[1:19:04] 4. Minimzing the number of tiles to build a shape
[2:31:39] 5. HW5(2): Assembly time, rank & concentrations