The Turing Machine Made Real, In LEGO

October 7, 2024 by Jenny List 19 Comments

The British mathematician and pioneer of computing Alan Turing published a paper in 1936 which described a Universal Machine, a theoretical model of a computer processor that would later become known as a Turing Machine. Practical computers don’t quite follow the design of a Turing Machine, but if we are prepared to sacrifice its need for an infinitely long paper tape it’s quite possible to build one. This is what [The Bananaman] has done using LEGO as a medium, and if you’d like one for yourself you can even vote for it on the LEGO ideas website.

There’s a video for the project which we’ve placed below, and it goes into quite some detail on the various mechanisms required. Indeed for someone used to physical machinery it’s a better explanation through seeing the various parts than many paper explanations. Not for the first time we’re bowled over by what is possible through the use of the LEGO precision mouldings, this is a machine which would have been difficult and expensive to build in the 1930s by individually machining all its parts.

With just shy of six thousand supporters and a hefty 763 days left at time of writing, there’s plenty of time for it to garner support. But if you want one don’t delay, boost the project by voting for it early.

Continue reading “The Turing Machine Made Real, In LEGO” →

A large array of triangles and colored lines showing the folding pattern of the origami computer

Turing Complete Origami

February 21, 2024 by Navarre Bartz 6 Comments

Origami can be an interesting starting point for a project, but we weren’t expecting [Thomas C. Hull] and [Inna Zakharevich]’s Turing complete origami computer.

Starting with the constraint of flat origami (the paper folds back on top of itself), the researchers designed a system that could replicate all the functionality of the previously-proven Turing complete Rule 110 automaton. The researchers walk us through the construction of AND, OR, NAND, NOR, and NOT gates via paper as well as the various “wires” and “gadgets” that connect the operators or filter out noise.

Everything ends up a large mess of triangles and hexagons with optional creases to make the whole thing work. While the origami computer probably won’t be helping you slice 3D prints anytime soon, much like a Magic computer, the engineering and math involved may prove useful in other applications.

We’re no strangers to origami here, having covered origami machines, medical robots, or using a desktop vinyl cutter to pre-score your project.

TMD-3: Clever Hall Sensor Hack Leads To Better Turing Demo

September 20, 2023 by Dan Maloney 4 Comments

We’ll beat everyone to the punch: yes, actually building a working Turing machine, especially one that uses a Raspberry Pi, is probably something that would have pushed [Alan Turing]’s buttons, and not in a good way. The Turing machine is, above all else, a thought experiment, an abstraction of how a mechanical computing machine could work. Building a working one seems to be missing the point.

Thankfully, [Michael Gardi] has ignored that message three times now, and with good reason: some people just grok abstract concepts better when they can lay their hands on something and manipulate it. His TMD-1 was based on 3D printed tiles with embedded magnets — arranging the tiles on a matrix containing Hall effect sensors programmed the finite state machine, with the “tape” concept represented by a strip of eight servo-controlled flip cards. While TMD-1 worked fine, it had some limitations, which [Mike] quickly remedied with TMD-2, a decidedly more complicated affair that used a Raspberry Pi, a camera, and OpenCV to read an expanded state machine with six symbols and six states, without breaking the budget on all the Hall sensors required.

TMD-3 refines the previous design, eschewing the machine vision approach and returning to the Hall effect roots of the original. But instead of using three sensors per tile, [Mike] determined that one sensor would suffice as long as he could mount the magnet at different depths within each tile. That way, the magnetic field for each symbol could be discerned by a single Hall sensor, greatly reducing complexity and expense. An LCD screen and a Raspberry Pi run a console app that shows the tape status, the state machine, and the state transitions.

[Mike] put a ton of work into this one — there are nineteen project logs — and he includes a lot of useful tips and tricks, like designing PCBs directly in KiCAD before even having a schematic. Of course, with a track record like his, we’d expect nothing less.

Continue reading “TMD-3: Clever Hall Sensor Hack Leads To Better Turing Demo” →

TMD-2: A Bigger, Better, More Collaborative Turing Machine

November 28, 2020 by Dan Maloney 3 Comments

One of the things we love best about the articles we publish on Hackaday is the dynamic that can develop between the hacker and the readers. At its best, the comment section of an article can be a model of collaborative effort, with readers’ ideas and suggestions making their way into version 2.0 of a build.

This collegial dynamic is very much on display with TMD-2, [Michael Gardi]’s latest iteration of his Turing machine demonstrator. We covered the original TMD-1 back in late summer, the idea of which was to serve as a physical embodiment of the Turing machine concept. Briefly, the TMD-1 represented the key “tape and head” concepts of the Turing machine with a console of servo-controlled flip tiles, the state of which was controlled by a three-state, three-symbol finite state machine.

TMD-1 was capable of simple programs that really demonstrated the principles of Turing machines, and it really seemed to catch on with readers. Based on the comments of one reader, [Newspaperman5], [Mike] started thinking bigger and better for TMD-2. He expanded the finite state machine to six states and six symbols, which meant coming up with something more scalable than the Hall-effect sensors and magnetic tiles of TMD-1.

TMD-2 has a camera for computer vision of the state machine tiles

[Mike] opted for optical character recognition using a Raspberry Pi cam along with Open CV and the Tesseract OCR engine. The original servo-driven tape didn’t scale well either, so that was replaced by a virtual tape displayed on a 7″ LCD display. The best part of the original, the tile-based FSM, was expanded but kept that tactile programming experience.

Hats off to [Mike] for tackling a project with so many technologies that were previously new to him, and for pulling off another great build. And kudos to [Newspaperman5] for the great suggestions that spurred him on.

TMD-1 Makes Turing Machine Concepts Easy To Understand

August 27, 2020 by Dan Maloney 10 Comments

For something that has been around since the 1930s and is so foundational to computer science, you’d think that the Turing machine, an abstraction for mechanical computation, would be easily understood. Making the abstract concepts easy to understand is what this Turing machine demonstrator aims to do.

The TMD-1 is a project that’s something of a departure from [Michael Gardi]’s usual fare, which has mostly been carefully crafted recreations of artifacts from the early days of computer history, like the Minivac 601 trainer and the DEC H-500 computer lab. The TMD-1 is, rather, a device that makes the principles of a Turing machine more concrete. To represent the concept of the “tape”, [Mike] used eight servo-controlled flip tiles. The “head” of the machine conceptually moves along the tape, its current position indicated by a lighted arrow while reading the status of the cell above it by polling the position of the servo.

Below the tape and head panel is the finite state machine through which the TMD-1 is programmed. [Mike] limited the machine to three states and ~~four transitions~~ three symbols, each of which is programmed by placing 3D-printed tiles on a matrix. Magnets were inserted into cavities during printing; Hall Effect sensors in the PCB below the matrix read the pattern of magnets to determine which tiles are where. The video below shows the TMD-1 counting from 0 to 10, which is enough to demonstrate the basics of Turing machines.

It’s hard not to comment on the irony of a Turing machine being run by an Arduino, but given that [Mike]’s goal was to make abstract concepts easy to understand, it makes perfect sense to leverage the platform rather than try to do this with discrete logic. And you can’t argue with results — TMD-1 made Turing machines clear to us for the first time.

Continue reading “TMD-1 Makes Turing Machine Concepts Easy To Understand” →

A (Card) Table-Top Turing Machine Of Magic: The Gathering Cards

July 18, 2019 by Roger Cheng 8 Comments

Within normal rules of collectible card game Magic: The Gathering a player may find themselves constrained to only a single legal course of action forward. It’s a situation players could craft to frustrate their opponents, though the victims usually break free after a few moves. But under a carefully crafted scenario, players would have no choice but to become the execution engine for a Turing-complete programming language written with Magic cards via techniques detailed in this paper.

One of the authors of this paper, [Alex Churchill], started working on this challenge in 2010. We covered an earlier iteration of his work here, and his own criticism that it was dependent on player cooperation. At various points, the game rules state a player “may” take certain actions and the construct falls apart if our player chooses the wrong thing. It would be as if a computer was built out of transistors that “may” switch as commanded or not, which would not be a very reliable method of computation.

To improve reliability of this particular Turing machine execution engine, the team combed through rules and cards to devise an encoding where the player is only ever presented with a single legal course forward. This ensures deterministic execution of the instruction stream, and now with proof of Turing-completeness in hand, we congratulate [Alex] on a successful conclusion to his decade-long quest.

We have a primer available for anyone who wants a refresher on Turing machines. They are utterly impractical but fun for hackers to build, and they are typically constructed of electronics and LEDs instead of ink on cardboard.

Via Ars Technica, who have presented their own analysis of this machine.

Main image: Unspecified set of Magic: The Gathering cards by [Robert] CC BY 2.0

A Two Tapes Turing Machine

February 23, 2018 by Jenny List 6 Comments

Though as with so many independent inventors the origins of computing can be said to have been arrived at through the work of many people, Alan Turing is certainly one of the foundational figures in computer science. His Turing machine was a thought-experiment computing device in which a program performs operations upon symbols printed on an infinite strip of tape, and can in theory calculate anything that any computer can.

In practice, we do not use Turing machines as our everyday computing platforms. A machine designed as an academic abstract exercise is not designed for efficiency. But that won’t stop Hackaday, and to prove that point [Olivier Bailleux] has done just that using readily available electronic components. His twin-tape Turing machine is presented on a large PCB, and is shown in the video below the break computing the first few numbers of the Fibonacci sequence.

The schematic is available as a PDF, and mostly comprises of 74-series logic chips with the tape contents being displayed as two rows of LEDs. The program is expressed as a pluggable diode matrix, but in a particularly neat manner he has used LEDs instead of traditional diodes, allowing us to see each instruction as it is accessed. The whole is a fascinating item for anyone wishing to learn about Turing machines, though we wish [Olivier] had given us a little more information in his write-up.

That fascination with Turing machines has manifested itself in numerous builds here over the years. Just a small selection are one using 3D printing, another using Lego, and a third using ball bearings. And of course, if you’d like instant gratification, take a look at the one Google put in one of their doodles for Turing’s 100th anniversary.

Continue reading “A Two Tapes Turing Machine” →