View source for Prototile

{{tiling/def}}

In the theory of [[tiling]]s a '''set of prototiles''', also called a '''protoset''',
is a (finite or infinite) set of tiles that represent (by congruence) all the tiles of a tiling, or of a class of tilings.

A protoset $ \P = \{P_k\} $ ''admits'' a tiling if there is a tiling $\T$ such
that all its tiles $T_i$ are congruent to some $P_k$.

==== Tiling problem ====

The tiling problem, i.e., the problem to determine whether a protoset admits a tiling is (algorithmically) undecidable,
both in general and for many special cases.
Normally, a protoset will (if at all) admit either a single tiling or uncountably many tilings, but intermediate numbers are also possible.
If a protoset admits (up to congruence) only a single tiling then it is called ''monomorphic'',
if it admits precisely two distinct tilings it called ''dimorphic'', ''trimorphic'' for three tilings, etc., 
$n$-morphic for $n$ tilings, and $\sigma$-morphic if there are countably many distinct tilings.