Hacker News new | past | comments | ask | show | jobs | submit login
Lego Turing Machine (legoofdoom.blogspot.com)
33 points by kqr2 on Jan 30, 2009 | hide | past | favorite | 11 comments



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.


You say that as if microprocessors aren't physical...


I suspect "mechanical" would be a better word. Microprocessors are mysterious black[1] boxen, whereas relays, etc, are macro-sized and can be made at home by hand.

[1] For some definition of "black".


I suspect "mechanical" would be a better word

Yes, exactly. Thank you.


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.


[deleted]


The funny part is - Order the Turing Machine today and you'll also receive...

- Infinite tape*

- Infinite storage*

- Unlimited computability*

*Subject to availability


The funny part is that real companies really get away with that obviously impossible lie (with caveat) so commonly that it works as a parody.


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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: