This person built a Turing Machine out of Lego, and has posted extensive build-notes.
Well, this Turing machine is not entirely mechanical... I used the RCX to store the transition table. Since the symbols are bar codes read with a light detector, it would have been very difficult to continue with a physical mechanism.Link (Thanks, Brad!)
Three subroutines are required, one to select which symbol to provide on top of the memory, one to turn the provider one quarter of a turn, and one to pull out one symbol from the bottom of the memory (reading it on the way).