Summary: Bricks are polyominoes with labelled cells. The problem of whether a given set of bricks is a code is undecidable in general. It is open for two-element sets. Here we consider sets consisting of square bricks only. We show that in this setting, the codicity of small sets (two bricks) is decidable, but 15 bricks are enough to make the problem undecidable. Thus the frontier between decidability and undecidability lies somewhere between these two numbers. Additionally we know that the codicity problem is decidable for sets with keys of size \(n\) when \(n=1\) and, under obvious constraints, for every \(n\). We prove that it is undecidable in the general case of sets with keys of size \(n\) when \(n \geq 6\).
For the entire collection see [Zbl 1053.68004].