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]

## About Rob Beschizza

Rob Beschizza is the Managing Editor of Boing Boing. He's

@beschizza on Twitter and can

be found on Facebook too. Email is dead, but you can try your luck at besc

...@gmail.com

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

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

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

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?