I think it could be really cool to make a physical representation of addressed memory, and then have a few op codes that can be used to solve basic problems. The op codes could be introduced as needed, and problems can grow in difficulty until actual compilation is necessary.

The program could be worked out by physically moving around paper strips with instructions written/erased/scratched-out/rewritten etc.