All the ones that I've seen (minecraft, dwarf fortress, little big planet) are 100% mechanical, so I guess all you need is the ability to move things around, plus some kind of basic physics, so that moving things around can have knock-on effects. Most of the DF ones are fluidic computers (http://en.wikipedia.org/wiki/MONIAC_Computer) and the rest are mostly falling blocks style. Quite Pratchett-esque.

I think Second Life is cheating though, because you can attach scripting code to objects.