Re:Lego Turing Machine
by mct on Friday January 30, 2009 @03:02AM
(#457858)
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.
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.
Re:Lego Turing Machine
by edgeztv on Friday January 30, 2009 @03:59AM
(#457899)
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 :)
[1] For some definition of "black".
Yes, exactly. Thank you.
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 :)
http://www.breakingrobots.net/projects/tmc/
Awesome use of an NXT.
- Infinite tape*
- Infinite storage*
- Unlimited computability*
*Subject to availability