Lego Turing Machine

I've spent some time pondering various methods of constructing a physical Turing Machine off and on for a couple years now, ever since I was introduced to them through mjd's Perl Quiz of the Week (http://perl.plover.com/qotw/r/024). However, all of my designs were deliberately non-electronic in nature. Personally, I find electromagnets, motors, and relays to all be aesthetically acceptable in this pursuit, but using a microprocessor to build a physical Turing Machine just somehow strikes me as... unappealing.

Interesting fact about TMs - while their computibility is equivalent to computers, the Big-O time for common algorithms is (possibly much) slower. Many O(n) tasks on computers with RAM are O(n^2) on a TM. The only commonality with computers in terms of time complexity is the Polynomial vs. Non-polynomial boundary.

The same is true for any model of computation.

Despite this equivalence, it's orders of magnitude harder to program a TM than the ugliest assembly language you've ever seen. This is one architecture that desperately needs a compiler :)

The A-team theme really changed this from the "Whoa, cool!" category to the rarefied "People need to see this NOW!" class.

Awesome use of an NXT.

I didn't like that it did not show some small computation like counting of 1 bits or any other trivial computation.

I love this one... So can we say now that 'computing is a child's play' ?