<p>A piece of Lego can be seen as a <a href="https://en.wikipedia.org/wiki/Polyomino" rel="noreferrer">Polyomino</a>: a plane geometric figure formed by joining one or more equal squares edge to edge.</p>
<p><a href="https://i.sstatic.net/stJI3.png" rel="noreferrer"><img src="https://i.sstatic.net/stJI3.png" alt="Polyomino" /></a></p>
<p>In <em>Tiling the Plane with a Fixed Number of Polyominoes</em> [2009], Nicolas Ollinger proved that 5 polyominoes are enough to simulate any set of <a href="https://en.wikipedia.org/wiki/Wang_tile" rel="noreferrer">Wang tiles</a> (the shapes of the polyominoes are quite complex and clearly depends on the set of Wang tiles to be simulated). And it is undecidable if a set of Wang tiles can tile the plane (see the <a href="https://en.wikipedia.org/wiki/Wang_tile#Domino_problem" rel="noreferrer">link</a> provided by domotorp in his comment).</p>
<p>So it is undecidable given a set of 5 &quot;Lego pieces&quot; (unlimited quantity of each) you can place them (theoretically) on an infinite Lego base and completely cover it (cover the plane).
In other words given a Turing machine, there is a set of 5 lego pieces such that you can cover the whole plane with them if and only if the Turing machine doesn't halt.</p>
<p>But even if you have only <em>3x1</em> Lego pieces, and a target object to recreate with them, it can be very hard to find the solution; indeed it is an NP-complete problem as proved in <a href="https://doi.org/10.1016/0925-7721(94)00015-N" rel="noreferrer">Danièle Beauquier, Maurice Nivat, Eric Rémila, Mike Robson; Tiling Figures of the Plane with Two Bars (1995)</a>.</p>

CC BY-SA 4.0
2021-04-04T20:45:38.447Z
2021-04-04T22:10:35.227Z
2021-04-04T22:10:35.227Z
Marzio De Biasi
<p>We know the concept of Turing Completeness. These days when I play lego with my kids. I realised that Lego is kinda like programming language: we can build a lot of things with a fairly small set of Lego shapes.</p>
<p>This makes me wonder, is there a math/computing theory similar to Turing Completeness for Lego: given a set of lego shapes, can we prove that, these lego shapes could generate all possible objects we can think of.</p>
<p>Obviously this idea sounds a bit silly. If this question is not suitable for this site, please help to point me to the right forum. Thanks!</p>

CC BY-SA 4.0
2021-03-28T06:14:31.977Z
Defined appropriately, they are Turing complete. You should read about the Domino problem: https://en.wikipedia.org/wiki/Wang_tile#Domino_problem
domotorp
CC BY-SA 4.0
2021-03-28T08:28:45.840Z
Do I get to play with [LEGO Mindstorms](https://www.lego.com/en-us/themes/mindstorms)?
Andrej Bauer
CC BY-SA 4.0
2021-03-29T07:05:21.247Z
Clearly the 1x1 block is not complete, and 1x2 is complete in theory but theory doesn't always work in practice.
Ville Salo
CC BY-SA 4.0
2021-03-29T19:38:51.790Z
@VilleSalo: Why do you think 1x2 is complete in theory? My intuition is that 1x2 wouldn't be complete (analogous to how 2SAT, 2COLORING, 2MATCHING aren't NP-complete, 2-TensorIso is not TI-complete, ...) but that something like 1x3 or maybe even 2x3 or 3x3 would be. Side note: the fact that I had such a reaction to a suggestion about 1x2 suggests that there is potentially a real definition lurking somewhere here!
Joshua Grochow
CC BY-SA 4.0
2021-03-30T04:38:10.050Z
I can build anything from 1x2 if gravity is lowered a bit. Note that it connects in four directions. (There may be parity issues but they don't affect universality.)
Ville Salo
<turing-machines>
Is there a concept of "Lego complete"? If not, does it make sense to develop one?
user152503
# Is there a concept of "Lego complete"? If not, does it make sense to develop one?

(Asked by: username_0 on 2021-03-27)

We know the concept of Turing Completeness. These days when I play lego with my kids. I realised that Lego is kinda like programming language: we can build a lot of things with a fairly small set of Lego shapes.

This makes me wonder, is there a math/computing theory similar to Turing Completeness for Lego: given a set of lego shapes, can we prove that, these lego shapes could generate all possible objects we can think of.

Obviously this idea sounds a bit silly. If this question is not suitable for this site, please help to point me to the right forum. Thanks!

**Tags:** turing-machines

> **Comments:**
> **username_1**: Defined appropriately, they are Turing complete. You should read about the Domino problem: https://en.wikipedia.org/wiki/Wang_tile#Domino_problem  
> **username_2**: Do I get to play with [LEGO Mindstorms](https://www.lego.com/en-us/themes/mindstorms)?  
> **username_3**: Clearly the 1x1 block is not complete, and 1x2 is complete in theory but theory doesn't always work in practice.  
> **username_4**: @VilleSalo: Why do you think 1x2 is complete in theory? My intuition is that 1x2 wouldn't be complete (analogous to how 2SAT, 2COLORING, 2MATCHING aren't NP-complete, 2-TensorIso is not TI-complete, ...) but that something like 1x3 or maybe even 2x3 or 3x3 would be. Side note: the fact that I had such a reaction to a suggestion about 1x2 suggests that there is potentially a real definition lurking somewhere here!  
> **username_3**: I can build anything from 1x2 if gravity is lowered a bit. Note that it connects in four directions. (There may be parity issues but they don't affect universality.)  

---

## 1 answers

### Answer by username_5 on 2021-04-04. Score: 5

A piece of Lego can be seen as a [Polyomino](https://en.wikipedia.org/wiki/Polyomino): a plane geometric figure formed by joining one or more equal squares edge to edge.

[![Polyomino](https://i.sstatic.net/stJI3.png)](https://i.sstatic.net/stJI3.png)

In *Tiling the Plane with a Fixed Number of Polyominoes* [2009], Nicolas Ollinger proved that 5 polyominoes are enough to simulate any set of [Wang tiles](https://en.wikipedia.org/wiki/Wang_tile) (the shapes of the polyominoes are quite complex and clearly depends on the set of Wang tiles to be simulated). And it is undecidable if a set of Wang tiles can tile the plane (see the [link](https://en.wikipedia.org/wiki/Wang_tile#Domino_problem) provided by username_1 in his comment).

So it is undecidable given a set of 5 "Lego pieces" (unlimited quantity of each) you can place them (theoretically) on an infinite Lego base and completely cover it (cover the plane).
In other words given a Turing machine, there is a set of 5 lego pieces such that you can cover the whole plane with them if and only if the Turing machine doesn't halt.

But even if you have only *3x1* Lego pieces, and a target object to recreate with them, it can be very hard to find the solution; indeed it is an NP-complete problem as proved in [Danièle Beauquier, Maurice Nivat, Eric Rémila, Mike Robson; Tiling Figures of the Plane with Two Bars (1995)](https://doi.org/10.1016/0925-7721(94)00015-N).


---

