Details

A Turing machine is an abstract model that can simulate any computer algorithm. Input and output data is stored on the same linear storage, called a "tape", which is manipulated by the machine according to a set of predetermined rules. The tape moves through a "read/write head" that reads then writes one data unit at a time.

The program of this computer consists of a matrix that for each character read by the read/write head and for each "internal state" (represented by a column of the matrix) has three items of data stored: • a new state for the machine • an output character to write back onto the tape • a direction into which the head has to move next, here given by an arrow pointing to the left, to the right, or down (signaling "don't move")

In principle, any possible sequential program can be processed in this way.

Binary numbers On the data tape of this Demonstration, binary numbers are written from right to left. Hence the number 3 in decimals is written as "11" in binary. Therefore, the rightmost ball placed in the row marked "1" has the value "1", the ball to the left of it has the value "2", the next has the value "4", the next "8", and so on.

Characters The ball bearings on the data tape represent the characters Star, Equal, One, Zero, and Blank (*, =, 1, 0, _), depending on which horizontal level the balls are positioned on. You can give these characters (and also the states of the program matrix) any names; the ones chosen here help to memorize their meanings.

Default setup In the default variant, the incoming data consists a string of ones (represented by black ball bearings placed in the row marked "1") on the tape, and the program matrix is designed so that the Turing machine converts it into a binary number, placed to the left of the given string and separated from it by one free space.

The input/output string in this basic Turing machine allows only five different characters to be used in the input string: blank, 0, 1, =, *. The program itself gives these signs the true meaning. The star, for example, can stand for any mathematical operator.

Start with the step-by-step tutorial Click the "Go" button at the lower left repeatedly to let the game guide you through the four steps of the Turing machine cycle. Keep clicking one of the buttons "Go" or "Run" until the Turing machine reaches the "Finish" state.

The machine works from one "state" (such as "Find", "Carry 1", "Go Back") to another using four steps at a time; this is called a "cycle". Once you understand the machine better, you can let the machine process one cycle (or ten cycles or more) with one click of the "Run" button. On the top right you select the number of cycles you want to process for each "Run" click, which is situated at the lower right.

This way you can leapfrog through the processing cycles. The areas of interest for each step are highlighted by a red circle. Keep on clicking one of the buttons "Go" or "Run" until the Turing machine reaches the "Finish" state.

Controls At the top left you select which variant (project) you want to see the machine process:

Variant 1: The machine converts a given string of ones into a binary number. Variant 2: The machine adds two given binary numbers. The two input numbers are separated by a star character. The resulting binary is placed to the left of the star's position. Variant 3: The machine subtracts two given binary numbers. Variant 4: The machine copies a given binary number. The copy will be positioned to the left of the original binary number, separated from the original number by a "=" character. Variant 5: the machine doubles a given binary number.

The "cycles" setter bar lets you choose how many cycles (multiples of four steps) are executed when you click one of the buttons "Go" or "Run". When the "error" or "finish" state is reached, the machine stops automatically. The number of processed cycles is displayed to the right of the "cycles" setter bar.

You can switch from clicking "Run" to clicking "Go" at any time, but clicking the "Go" button while "Run" is active will have no effect. In this case, you have to go back to the start first, then click "Go".

Go back to start To go back to the start, simply click the area between the "Go" button and the "Run" button.

Editing the "data tape" To change the data input, simply click one of the black ball bearings. Then run the machine and see how the result differs depending on the input. It is strongly recommended that you edit only before you start the processing (i.e. before you click the "Go" or the "Run" button); anything else can lead to unpredictable outcomes.

History of a real Turing machine I built in 1986 The Turing machine is named after Alan Turing, who was one of the founders of modern computer science and information theory and investigated the many possibilities of this machine.

In principle, the tape has infinite length, at least at one end. The machine was limited to using only up to five different characters. If we allow more characters, then the input would request a larger matrix. The number of states (matrix columns) also changes with the program.

In 1986, I built a mechanical Turing machine from a metal construction set, plastic pipes, strings, springs, and pieces of wood. The tape was a carrier that glided over rollers. The read/write head was fixed. Ball bearings were used (as indicated in this game) as input and output data, one sitting in each of five indentations of one little wooden stick per character, which was tipped over to let the ball roll out into one of five places where its position could be checked, mirroring the position it had on the tape. (My machine did not have the central narrow version of a tape shown in this Demonstration. It is included in this Demonstration for clarity of reading and understanding.)

This ball was then also used for triggering the setting of the markers for the inner state (matrix column) and the input character given (matrix row). This was done by lifting it onto the top of the 1.5 m construction and letting it roll into a matrix of holes connected to a grid of plastic pipes. When the ball left the pipe, it was stopped and the and coordinates of its position mechanically determined. This defined the new state and the new output, all of this being achieved mechanically by pulling levers, which were activated by pulling strings.

In a similar second step (dropping the ball through more pipes), the direction of the next carrier (moving underneath the read/write head) movement was determined and then executed. The pipe matrix was removable to allow for a quick exchange of programs.

Clicking "Run" in this Demonstration, which leads you through the process in small steps, was thus replaced by pulling 12 strings, one after the other, proving that some ancient Greek philosopher could have built this computer!

This unique piece of craftsmanship was for a while displayed at the entrance of the Computer and Information Science Department of the University of Heidelberg, Germany, which bought it from me. I do not know its current location.

Associated Zillions games "Turing Machine" and "Turing Machine II" were published as a Zillions game by the author in January 2002.