# Is there a concept of “Lego complete”? If not, does it make sense to develop one?

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!

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