Turing machine

15 Articles

The Collatz-O-Matic: A State Machine With Style!

October 10, 2016 by 2 Comments

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!

collatz-o-matic-closeupThe 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:

  1. Delete two symbols (tags) from the front of the queue.
  2. If the first symbol deleted was:
    1. A – then write BC to the rear of the queue
    2. B – then write A to the rear of the queue
    3. 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 Turing Tapes

August 18, 2016 by 27 Comments

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

A Very Modern Turing Machine Build

July 12, 2016 by 17 Comments

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

The Computer Without A CPU

April 20, 2014 by 31 Comments

1bit

[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!

 

Turbot Is A Beam/Picaxe Hybrid

October 13, 2013 by 18 Comments

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

Building A Turing Machine From Magic The Gathering

September 12, 2012 by 8 Comments

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!

[via Slashdot]

A LEGO Turing Machine For [Alan]’s Centennial

June 18, 2012 by 12 Comments

2012 is the 100-year anniversary of [Alan Turing]’s birth, and to celebrate the centennial, [Jeroen] and [Davy] over at Centrum Wiskunde & Informatica in The Netherlands built a Turing machine out of LEGO.

A Turing machine is an extremely simple device, but is still able to compute everything your desktop can. The machine is generally described as an infinite paper tape with a read/write head. On this paper tape, the numbers ‘1’ and ‘0’ are written. By precisely defining what the Turing machine should do when it comes across a ‘1’ or ‘0’, its able to do the same calculations as a laptop, albeit at a much slower rate.

The LEGO Turing machine has a series of pins signifying each bit. These pins are moved underneath a read/write head containing a light sensor and robotic arm. When a pin is down, the camera sees a dark spot signifying one state. When the pin is up, light reflects off a white LEGO piece signifying another state.

[Jeroen] and [Davy] built an IDE for their Turing machine, so if you’ve got a few LEGO NTX bricks lying around you can grab the Git and build your own. Check out the mini documentary after the break.

Continue reading “A LEGO Turing Machine For [Alan]’s Centennial” →