Speaker
Prof.
Jarkko Kari
(University of Turku)
Description
We consider the algorithmic problem of determining if a
given self-assembly system is terminating, that is, if an
unbounded growth may happen or not. We prove that this
question is undecidable even in the simple tiling model of
self-assembly, by showing that no algorithm is able to
determine if a given set of Wang tiles can form on the plane
an infinite path where consecutive tiles match with each
other. We also consider the analogous problem of determining
whether given tiles can form a correctly tiled loop, and
prove its undecidability.
Primary author
Prof.
Jarkko Kari
(University of Turku)
