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
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”