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”
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.
- If the first symbol deleted was:
- A – then write BC to the rear of the queue
- B – then write A to the rear of the queue
- C – then write AAA to the rear of the queue
Numbers are as easily represented as any other symbol, and the Collatz conjecture is that no matter what integer you start with, the system (probably) always eventually reaches state 1. There is video of the device demonstrating exactly that embedded below. Continue reading “The Collatz-O-Matic: a State Machine with Style!”
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.
Continue reading “The Turing Tapes”
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.
Continue reading “A Very Modern Turing Machine Build”
[Jeff Laughton] was contacted by a customer that was interested in adding some automated functions to a printing press. Before eventually settling on a microcontroller for the job, [Jeff] went old school and started looking at logic gates, counters, and flip-flops. This lead him to the Motorola 14500 industrial control unit, a minimal processor with only 16 instructions. After a few ‘back of the napkin’ sketches, he came up with an extremely minimal computer that doesn’t use a microprocessor. It’s an interesting design notable not only for its electronic brevity, but also because it only uses one instruction.
The only instruction this computer will ever execute is an input test, the result of which controls a two-way branch. Instructions consist of an input address, output address, and a single bit of data. If the data bit is true, the computer jumps to one location in ROM, and if the data bit is false, a jump to another location is executed.
A computer really isn’t a computer without some form of memory, and this design is no exception. [Jeff] managed to add two bits of data between the 8-bit latch and 8-bit multiplexer in the design. This is enough to call a few subroutines which test the I/O-mapped memory to decide what the next instruction should be.
It’s a truly bizarre design, but actually much closer to a true Turing machine than the computers in your pocket, on your wrist, on your desk, and in your car.
Thanks [James] for the tip!
[James] wanted to build a BEAM turbot. He ran into some problems with the BEAM circuitry though, and ended up with a BEAM/Picaxe hybrid.
Beam robotics are the brainchild of Mark Tilden. The acronym stands for Biology, Electronics, Aesthetics, and Mechanics. BEAM based bots were very popular with hobbyists in the 90’s and early 2000’s, but popularity has since died down. BEAM robots tend not to use microcontrollers, instead attempting to simplify things down to the lowest number of elements.
[James’] turbot uses a miller solar engine. The original design used the engine to drive a Solar Turbot Latch. [James’] problem was that the photodiode “eyes” of the robot were not properly enabling the 74AC245 to pass current to the motor. Since the robot was built in a tiny space, debugging the circuit was extremely hard. After struggling with the ‘245 for some time, [James] decided to swich out the BEAM circuit for a Picaxe microcontroller.
The Picaxe can only sink or source about 20ma per pin, which is slightly less than the no load current of [James’] motors. To make up for this, he ganged up four pins per motor. There was some risk in the motors blowing up the Picaxe. However between the lightly loaded gearmotors and low current solar panels it seems to be working just fine. Overall the bot is a very clean, compact build. Jump past the break to check out its really smooth crablike walking action.
Continue reading “Turbot is a Beam/Picaxe Hybrid”
If you really know your Magic the Gather and you’re a programming wiz you’ll appreciate this paper on building a functioning Turing Machine from Magic the Gathering cards. We’re sure you’re familiar with Turing Machines, which uses a rewritable strip to store and recall data. Most of the time we see these machines built as… machines. For instance, this dry-erase marker Turing Machine has long been on the top of our favorites list. But as The Diamond Age by Neal Stephenson illustrates, there’s more than one way to skin this cat.
A complete list of the cards used in this machine can be found here. A little bit of preparation (casting to tweak abilities) goes into making sure the cards will work as called for in the Turing design. The tape is made of Ally tokens to the right of the head, and Zombie tokens to the left. The computational abilities of the head depend on the colors of the cards. It’s a bit too complex to paraphrase, but the design is based on this 2-state, 3-symbol setup whose rules are listed in the image above.
It’s going to take us a while to fully wrap our heads around this thing, but it’ll be fun getting to that point!