Froebel’s Gifts were meant to be given in a particular order, growing more complex over time and teaching different lessons about shape, structure and perception along the way. A soft knitted ball could be given to a child just six weeks old, followed by a wooden ball and then a cube, illustrating similarities and differences in shapes and materials. Then kids would get a cylinder (which combines elements of both the ball and the cube) and it would blow their little minds. Some objects were pierced by strings or rods so kids could spin them and see how one shapes morphs into another when set into motion. Later came cubes made up of smaller cubes and other hybrids, showing children how parts relate to a whole through deconstruction and reassembly.
These perception-oriented “Gifts” would then give way to construction-oriented “Occupations.” Kids would be told to build things out of materials like paper, string, wire, or little sticks and peas that could be connected and stacked into structures.
Wang tiles (Hao Wang, 1961) are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them.
The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether an entire infinite plane can be filled this way. The next question is whether this can be done in a periodic pattern.
In 1966, Wang's student Robert Berger solved the problem in the negative. He proved that no algorithm for the problem can exist, by showing how to translate any Turing machine into a set of Wang tiles that tiles the plane if and only if the Turing machine does not halt. The undecidability of the halting problem then implies the undecidability of Wang's tiling problem.