Embedded Files
A Turing machine is a mathematical model, an abstract machine, that can be used to perform computations. Alan Turing described the model in 1936. It is supposed to model computation itself, which makes it useful when we are talking about computers. Anything a computer can compute, can be computed with a Turing machine, and the limitations of Turing machines apply to computers as well. In other words, a Turing machine models what a computer is able to do.
Informally, a Turing machine can be described as having the following components:
An infinite tape that is divided into cells that can each hold a symbol
A finite alphabet of symbols.
A symbol that is called the blank, which is part of the tape but not part of the alphabet
A tape head that can read one of the tape cells at a time.
A finite set of states, containing a start state and final state(s).
Upon reading the symbol, a symbol can be written at the position of the tape head. The tape head can move to the left or to the right and the machine can change state. These actions all depend on the state the machine is in.
I wanted to build a physical rendition of the system that is intended to demonstrate how a Turing machine works. Building a system that you can watch as it performs computations also has a certain aesthetic, in my eyes.
The tape can be moved to the left and the right by a stepper motor (left)
You immediately run into problems when you try to implement this model in the real world: there is no way to create an infinite storage space, although you can certainly give the suggestion of a storage space that is extendable. The prototype I built depends on the actions of both a computer and a human. I chose to use coloured pieces of paper as symbols to demonstrate that they need not necessarily be numbers or letters. An additional advantage is that colour communicates in a more direct way. The blank symbol is a blue piece of paper and the alphabet contains red and green as symbols. The pieces of paper are attached to a belt that can be moved to the left or right by a stepper motor that is connected to an Arduino.
A colour sensor, connected to an Arduino, detects the colour and thus performs the role of the tape head. Depending on the state the system is in, the Arduino gives a command to the human to replace the detected coloured piece of paper by another one. Then the belt is moved to the left or right and the state of the system is changed. The colour of the piece of paper that is currently in front of the sensor is detected, and new commands are given. This loop is repeated until the system enters its final state.
The prototype performs the calculation +1, if we look at the coloured pieces of paper as representing binary numbers, with red representing 1 and green 0. The start and end states are defined as being at a blank symbol on the right of the "number" that is represented by the coloured pieces of paper. See the table of system states below for details.
Equipment: stepper motor, motor shield, Arduino, colour sensor
Detecting the colour
Future development
If the machine could swap colours by itself, this would make it more convincing. Because it would make the prototype technically more complex, I considered achieving this with LED lights in the prototype. However, that would mean that the system would already be aware of the symbols that the tape contains, making a sensor/tape head unnecessary and detracting from the accuracy of the model. In a future version this should be implemented, as well as making the system more robust by using different materials. Additionally, displaying the current state of the system next to a table containing the actions of the system depending on its state would make the system more informative to the viewer.
Table of system states
Page updated
Google Sites
Report abuse