"Mathematician Alan M. Turing was one of the first to propose the idea of a universal mathematics machine. Turing and Emil Post independently proved that determining the decidability of mathematical propositions is equivalent to asking what sorts of sequences of a finite number of symbols can be recognized by an abstract machine with a finite set of instructions. Such a mechanism is now known as a Turing machine.
"A Turing machine can be pictured as a black box capable of reading, printing, and erasing symbols on a single, long tape or strip of paper divided by lines into square cells, or boxes. Each cell is blank or contains one symbol from a finite alphabet of symbols.
"The Turing machine scans the tape, one cell at a time, usually beginning at the cell furthest to the left that contains a symbol. The machine can leave the beginning symbol unchanged, erase it, or print another in its place. If in reading the tape the machine later encounters a blank cell, then the machine has the choice of leaving the cell empty or entering a symbol. After it performs its assigned task on a given cell, the machine stops or else moves one cell to the left or right.
"What the machine does to a cell and which way it moves afterward depends on the state of the machine at that instant. Like a state of mind, the machine's internal configuration establishes the environment in which a decision is made. Turing machines are restricted to a finite number of states.
"An action table stipulates what a machine will do for each possible combination of symbol and state. The first part of the instruction specifies what the machine should write, if anything, depending on which symbol the machine sees. The second part specifies whether the machine stays in the same state or shifts to another state, which usually has a different set of instructions.
"Suppose a Turing machine must add two integers. There are numerous different ways in which this can be done, depending on how many symbols and states are allowed. One of the simplets possibilities is to represent an integer by a string of asterisks. Thus, *** would be 3, and **** would be 4. To add 3 and 4, *** and **** are first printed on a tape, with a blank space between the two strings. The machine then fills in the blank cell by printing a * and goes to the end of the string of sasterisks and erases the last one in the row. What's left is the requeired answer: a set of 7 asterisks.
"An action table instructs the machine how to perform the addition. The table's first column gives the machine's possible mental states, and the first row lists all the symbols being used. In this example, there are only two symbols: and asterisk * and a blank. Each combination of symbol and state specifies what, if anything, needs to be done to a cell, in which direction to move after the action, and the state of the machine, that is, which set of instructions it will follow for its next move.
" .--------------------------------------------------------------------------. | ____________Symbol_________________________ | | * Blank | | | | State 0 right, state 0 print *, right, state 1 | | State 1 right, state 1 left, state 2 | | State 2 erase, stop --- | | | `--------------------------------------------------------------------------'
"The machine begins in state 0 and scans the * farthest to the left on the tape. According to the instructions for state 0 and symbol *, the machine leaves the symbol as it is, shifts one step to the right, and remains in state 0. It encounters another *, and the process is repeated. Finally, it reaches the blank cell. From the table, the machine knows it must print a *, then move one space to the right. This time, however, it shifts into a new state. Now the machine statys in state 1 until, step by step, it reaches the first black at the end of the string. This time, it backs up one space and shifts into state 2. It erases the cell's asterisk and stops. The addition is complete (see Figure 7.14).
".-------------------------------------------------------------------------. | State M | | v | | 0 | | * | * | * | | * | * | * | * | | | | | v | | 0 | | * | * | * | | * | * | * | * | | | | | v | | 0 | | * | * | * | | * | * | * | * | | | | | v | | 0 | | * | * | * | | * | * | * | * | | | | | v | | 1 | | * | * | * | * | * | * | * | * | | | | | v | | 1 | | * | * | * | * | * | * | * | * | | | | | v | | 1 | | * | * | * | * | * | * | * | * | | | | | v | | 1 | | * | * | * | * | * | * | * | * | | | | | v | | 1 | | * | * | * | * | * | * | * | * | | | | | v | | 2 | | * | * | * | * | * | * | * | * | | | | | v | | Halt | | * | * | * | * | * | * | * | | | | | `-------------------------------------------------------------------------' "Figure 7.14 At each step, a Turing machine may move one space to the left or right. By following a simple set of rules, the machine can add two numbers, starting with separate groups of three and four asterisks and ending up with one group of seven asterisks."
"The same action table can generate the sum of any two whole numbers, no matter what their size. But adding two numbers such as 49,985 and 51,664, by itself, would require a tape with at least 100,000 cells, To be capable of adding any two numbers, the tape would have to be infinitely long. In fact, a universal Turing machine capable of any mathematical operation, must have an infinitely long tape. An ordinary computer, with a limited amount of memory, lacks this property.
"Similar tables can be worked out for subtraction and for practically any other mathematical operation. The sole condition is that the number of states and symbols listed in such a table is finite, which ensures that a routine, mechancial process can do the job. Often, several different tables can be used to perform a certain operation."
[IP] Peterson, Ivars. The Mathematical Tourist: snapshots of modern
mathematics. W. H Freeman and Co. 1988. New York. pp 195-196.
prepared by Jonathan Steidel
( jsteidel@science.gmu.edu )