Many of the games that I find inspirational are based on physics simulations. The example I'm most fond of is The Incredible Machine, which I played as the Windows sequel The Even More Incredible Machine. It allows the player to arrange various objects and provides a limited physics simulation to show what happens when the "machine" goes into motion. There is a wide variety of ramps, balls, explosives, and (Sch)lemmings to choose from. Importantly, however, the freeplay mode is a minor component.
The real meat of the game is a series of challenges that restrict you to a small group of objects, and require you to accomplish some feat (get the ball through the hoop, feed the cat). Many of these have multiple solutions, and they encourage full exploration of the possibilities offered by objects and combinations thereof. The Incredible Machine and similar physics games work so well because they can explicitly present a problem, they get much of the possibility space for free due to physical intuition, and debugging is absolutely straightforward.
What would an "Incredible Machine for programming" look like? I submit Rocky's Boots as an intermediate example. This Apple II game was designed by Warren Robinett, who invented the action adventure game with the original Atari VCS Adventure. Rocky's Boots is set up similarly to Adventure, with an interconnected set of screens filled with interactive objects. Instead of the objects being swords, keys, and dragons, they are logic gates, sensors, buzzers, and clocks. As in Adventure, the player's square cursor is the means for picking up objects, they can also be snapped together to build circuits.
The cursor has an additional property, however: it is orange. Orange represents "on" in the visual metaphor of the game, and Robinett describes it
as if the electricity was liquid orange fire flowing through transparent pipes. Thus the player incidentally probes parts of circuits as he encounters wires. "On" wires turn from white to orange, and this impulse travels along the circuit as the logic gates switch. Even if no effector is attached to the output of the circuit, the simulation is always running to show how things behave. The consistent and even superfluous demonstration of behavior helps to build up the player's intuitions.
When I discussed my game design ambitions with Ken Perlin, he referred me to a video made by Atari Cambridge Research back in 1984, to illustrate just how long these ideas have been around. This video shows (at around 3 minutes) an interesting combination of Logo with Rocky's Boots. Logo is most interesting due to its emphasis on the physical or virtual navigation of the turtle, which aids development and debugging due to spatial intuition. We find this reflected in the vast majority of introductory programming environments and games that involve commanding a robot to move around: Karel, Kodu, ChipWits and Light-Bot to name very few.
While the Atari Cambridge Research demo isn't a game, the concept is readily applicable to one. A "button box" of commands for the turtle to follow, combined with the ability to build systems that activate these commands for you, provides all the elements needed to build up a simple programming system. One element that I feel was overlooked is for the turtle itself to be an agent just as the player is; this closes the circle in a consistent way.
Even if we can deal with simple programs, the difficulty lies in being able to build complex structures. Any sufficiently complex physics sim, like Minecraft or Little Big Planet, can host microprocessors. We can even imagine designing a series of challenges that leads up to such a thing. But the vastness and complexity of these systems is completely beyond what we can expect any but the most dedicated player to pursue. Still, we have incredible techniques for managing complexity across engineering, mathematics, and computer science. I hope that a game designed to communicate these powerful ideas can make a difference.