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!

  • 5
    $\begingroup$ Defined appropriately, they are Turing complete. You should read about the Domino problem: en.wikipedia.org/wiki/Wang_tile#Domino_problem $\endgroup$ – domotorp Mar 28 at 6:14
  • 1
    $\begingroup$ Do I get to play with LEGO Mindstorms? $\endgroup$ – Andrej Bauer Mar 28 at 8:28
  • $\begingroup$ Clearly the 1x1 block is not complete, and 1x2 is complete in theory but theory doesn't always work in practice. $\endgroup$ – Ville Salo Mar 29 at 7:05
  • $\begingroup$ @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! $\endgroup$ – Joshua Grochow Mar 29 at 19:38
  • $\begingroup$ 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.) $\endgroup$ – Ville Salo Mar 30 at 4:38

A piece of Lego can be seen as a Polyomino: a plane geometric figure formed by joining one or more equal squares edge to edge.


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 (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 provided by domotorp 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.