LEGO Turing machine crunches the numbers

A Turing machine is a basic device able to perform fundamental computing operations; they're super because they demonstrate the abstract concepts of compuer science in the flesh. Make's relentlessly wonderful catalog of strange machines today gives us one made of LEGO, by "Denis."

Instead of having a bi directional tape, it uses a stack. When the symbol beneath the stack is read (and removed), the machine changes "states" and can add zero, one or two symbols on top of the stack.

This variation is maybe very different yet it is possible to show that this simple machine has the same capabilities than a Turing machine. Among other things, it can emulate a Turing machine placed on the stack.

How many billions of these would be needed to run Doom at at least 1 frame per universe?

LEGO Turing Machine [Make]

[#1 posted by Brian Copeland , June 12, 2008 6:58 AM]

Ack, where's the video? That screams for a video.

But in October 2007, someone finally proved that a 2 state, 3 symbol Turing Machine is universal. Given the example the author used, this one would certainly qualify. So that puppy can technically run any computable program.

But wouldn't Lego Star Wars be some recursive awesomeness?

[#2 posted by Smurf , June 12, 2008 10:00 AM]

You can't run Doom on one of these machines: you'd need a stack so large it'd implode into a black hole.

[#3 posted by dculberson , June 12, 2008 12:18 PM]

Smurf, thus letting the demons out into your research station, and starting real-life Doom!

[#4 posted by Anonymous , July 10, 2008 2:03 AM]

Do you really think that your machine is euqivalent to a turing machine? What is the symbol beneath the stack? Is this the first symbol on the ground of the stack or what?
Best regards
Andre Betz