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.
[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.
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.
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.
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.
If you have ever thought that working out a Collatz sequence by hand was alright but lacked buttons and lights, the Collatz-o-matic by [mechatronicsguy] has you covered!
The device is a type of Tag system calculator. [mechatronicsguy] explains that a Tag system is a method of computing similar to a Turing machine; it consists of a read & write FIFO array (or tape or queue) of indeterminate length, and at every step the system reads the symbol at the “head”, deletes a fixed number of symbols from the “head”, and depending on what that first symbol was, appends one or more symbols to the “tail”. Then the process repeats with whatever new symbol is at the head.
The Collatz-o-Matic uses an RGB LED string to represent the queue, and is set up in the following way:
Delete two symbols (tags) from the front of the queue.
The recent movie “The Imitation Game” gave [Alan Turing] some well-deserved fame among non-computer types (although the historical accuracy of that movie is poor, at best; there have been several comparisons between the movie and reality). However, for people in the computer industry, Turing was famous for more than just helping to crack Enigma. His theoretical work on computing led to the Turing machine, which is still an important concept for reasoning about computers in a mathematical way. He also laid the foundation for the stored program computer that we take for granted today.
What’s a Turing Machine?
A Turing machine is deceptively simple and, like many mathematical models, highly impractical. Leading off the inpracticalities, the machine includes an infinite paper tape. There is a head that can read and write any symbol to the tape at some position, and the tape can move to the left or the right. Keep in mind that the head can write a symbol over another symbol, so that’s another practical difficulty, although not an insurmountable one. The other issue is that the symbol can be anything: a letter, a number, a jolly wrencher, or a bunch of dots. Again, not impossible, but difficult to do with practical hardware implementations.
Mathematicians. If you let them use the concept of infinity, there’s almost nothing they won’t be able to prove. Case in point: the Turing machine. The idea is that with an infinite length of tape, one could build a thought-experiment machine with only a few instructions that should be able to compute anything that’s computable.
[Igor]’s Turing machine is one of the nicest we’ve ever seen built. The “tape” is significantly shorter than infinity, which limits the computations he can achieve, the use of 3D printing, electric contacts, and WS2812 RGB LEDs for the tape are profoundly satisfying.
A bit on the tape is portrayed as unused if the LED is off, zero if it is red, and one if it is green. Each station on the tape is indexed by a set of blue LEDs observed by the gantry of the writing head which uses a 3D printed finger and motor to change the state of each bit. Programs are stored on a home-built punch card, which gets extra geek points from us.
Watch it run through “busy beaver” (embedded below) and tell us that it’s not awesome, even if it is a couple of LEDs short of infinity.