{TALK
	   {"October 2}
           {"Complex tiling: breaking translational symmetry}
           {"Leonid Levin}
           {"Boston University}
	   {"(lnd@cs).bu.edu (correct in an obvious way)}
	   {"
A tile is a unit size square with colored edges. A palette P is a finite
set of tiles with copies of which one can tile the plane so that the
colors of adjacent tiles match. Classical works constructed palettes
that can tile an infinite plane, but cannot do this recursively.
 That is, consider all P-squares, i.e. those appearing in P-tilings of a
plane. For any c, only P-squares of bounded size can be generated (from
their diameter) by c-bit programs. We pushed these results to the limit,
with a palette for which all such squares have diameter c or less.
 This bound is tight since specifying the tiles on the square's frame
suffices for tiling the square recursively. Thus, this palette allows
only tilings with all frames being "nearly-random".
<p>
My talk, however, will only briefly mention this our result.
I will mostly talk about just one old tool we are using:
a palette P which precludes any translational symmetry in any P-tiling.
The set of all P-tilings is, of course, symmetric under translations.
Yet, any specific P-tiling is aperiodic, this symmetry spontaneously
broken. Classical proofs of this result are very cumbersome.
I will try to present a more transparent construction and proof.
<p>
Joint work with Bruno Durand and Alexander Shen.
}
}