Some people have managed to create working CPUs (or ALUs) in Minecraft. They're slow and have little computing power or memory, but I still think it's an interesting case of recursion. Minecraft simulates a physical world, and these are computers created within the confines, and conforming to the rules of that world.
In any case, some links to information/videos about creating CPUs (and ALUs) in Minecraft follow.
An 8-bit CPU:
And a webpage about it: http://lazcraft.info/tagged/CPU
(This is the project with most information.)
A 16-bit CPU:
Here's the Youtube channel connected with this project: http://www.youtube.com/user/theinternetftw
A 32-bit ALU:
And, finally, it's not a computer, but a pretty cool implementation of Conway's Game of Life in Minecraft:
Conway's Game of Life in Minecraft:
Let me know about other CPUs/ALUs etc. in the comments.