Turing Machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.
The "Turing" machine was described by Alan Turing in 1936,[1] who called it an "a(utomatic)-machine". The Turing machine is not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation.
Turing gave a succinct definition of the experiment in his 1948 essay, "Intelligent Machinery". Referring to his 1936 publication, Turing wrote that the Turing machine, here called a Logical Computing Machine, consisted of:
...an infinite memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.[2] (Turing 1948, p. 61)
A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically-oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or 'mechanical procedure'.
A Turing machine is an idealized computing device consisting of a read/write head (or 'scanner') with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol--'0' or '1', for example. This tape is the machine's general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation.
The input that is inscribed on the tape before the computation starts must consist of a finite number of symbols. However, the tape is of unbounded length--for Turing's aim was to show that there are tasks that these machines are unable to perform, even given unlimited working memory and unlimited time.
The read/write head is programmable. It is be helpful to think of the operation of programming as consisting of altering the head's internal wiring by means of a plugboard arrangement. To compute with the device, you program it, inscribe the input on the tape (in binary or decimal code, say), place the head over the square containing the leftmost input symbol, and set the machine in motion. Once the computation is completed, the machine will come to a halt with the head positioned over the square containing the leftmost symbol of the output (or elsewhere if so programmed).
States
The head contains a subdevice that I call the indicator. This is a second form of working memory. The indicator can be set to any one of a number of 'positions'. In Turing machine jargon, the position of the indicator at any time is called the state of the machine at that time. To give a simple example of the indicator's function, it may be used to keep track of whether the symbol last encountered was '0' or '1'. If '0', the indicator is set to its first position, and if '1', to its second position.
Atomic operations
There are just six types of fundamental operation that a Turing machine performs in the course of a computation. It can:
- read (i.e. identify) the symbol currently under the head
- write a symbol on the square currently under the head (after first deleting the symbol already written there, if any)
- move the tape left one square
- move the tape right one square
- change state
- halt.
These are called the primitive or atomic operations of the machine. A complicated computation may consist of hundreds of thousands, or even millions, of occurences of these atoms
Commercially available computers are hard-wired to perform primitive operations considerably more sophisticated than those of a Turing machine--add, multiply, decrement, store-at-address, branch, and so forth. The precise constitution of the list of primitives varies from manufacturer to manufacturer. It is a remarkable fact that none of these computers can outdo a Turing machine. Despite the Turing machine's austere simplicity, it is capable of computing anything that any computer on the market can compute.
Indeed, since it is an abstract or notional machine, a Turing machine can compute more than any physical computer. This is because (1) the physical computer has access to only a bounded amount of memory, and (2) the physical computer's speed of operation is limited by various real-world constraints.
It is sometimes said, incorrectly, that a Turing machine is necessarily slow, since the head is continually shuffling backwards and forwards, one square at a time, along a tape of unbounded length. But since a Turing machine is an idealised device, it has no real-world constraints on its speed of operation.
The instruction table
A program or 'instruction table' for a Turing machine is a finite collection of instructions, each calling for certain atomic operations to be performed if certain conditions are met. Every instruction is of the form:
If the current state is n and the symbol currently under the head is x, then write y on the square currently under the head [y may be identical to x], go into state m [m may be n], and - - - .
In place of - - - may be written either 'move left one square' or 'move right one square' or 'halt'.
An example
The machine in this example starts work with a blank tape. The tape is endless. The problem is to set up the machine so that if the scanner is positioned over any square and the machine is set in motion, it will print alternating binary digits on its tape, 0 1 0 1 0 1..., working to the right from its starting place, and leaving a blank square in between each digit.
In order to do its work the machine makes use of four states, labelled 'a', 'b', 'c' and 'd'. The machine is in state a when it starts work.
The table of instructions for this machine is as follows.The top line of the table reads: if you are in state a and the square you are scanning is blank then print 0 on the scanned square, move right one square, and go into state b. state | scanned symbol | print | move | next state |
a | blank | 0 | R | b |
b | blank | R | c | |
c | blank | 1 | R | d |
d | blank | R | a |
A machine acting in accordance with this table of instructions toils endlessly on, printing the desired sequence of digits and leaving alternate squares blank.
Variants of Turing Machine
Turing Machines are the simplest formally defined model which is capable of computing anything that modern computers can compute. This makes them useful for theoretical study. However, devising a Turing Machine that solves a given problem of interest is not always easy. Therefore, there exist several common variants of Turing Machines which have been proven to be equivalent in computational power to a Turing Machine, but provide much more flexibility by increasing the types of steps that can be added to an Turing Machine algorithm. Proofs that a computational model is equivalent in power to a Turing Machine generally involve showing how to construct a Turing Machine given any possible instance of the model. Sometimes devising an algorithm to solve a problem using one of these is far easier, and since we know that they can be converted to a Turing Machine, we don't need to do all that extra work.
A list of common Turing Machine variants, otherwise known as Turing Equivalent machines:
- Non Deterministic Turing Machine - A Turing Machine which may follow more than one transition per configuration.
- Multitape Turing Machine - A Turing Machine containing a finite number of tapes greater than 1.
- Universal Turing Machine - A Turing Machine that is able to store any other Turing Machine on its tape and emulates its function. This is also related to the Recursion Theorem and is one of the more broadly useful (and important) constructs in Computational Theory.
- Enumerator - A Turing Machine which has a printer attached and prints out lists of strings.
These are useful models in the Theory of Computation, but really any programming language which describes only algorithms (which is all of them, currently) could be considered a Turing Machine variant. Arbitrary languages tend to be far less useful for Theory than the aforementioned machines, so I don't list them.
Less Powerful Computational Models
Turing Machines can also describe less powerful models of computation which can solve subsets of the problems which Turing Machines can solve. These other models can be more practical in terms of hardware costs and implementation, and form the basis for the abundant simple electronic devices that far outnumber computers. Studying what these types of machines can solve is also important, because we can we can know more about their function in general than we can about Turing Machines.
Hilbert's Problem
Hilbert's problems ranged greatly in topic and precision. Some of them are propounded precisely enough to enable a clear affirmative/negative answer, like the 3rd problem (probably the easiest for a nonspecialist to understand and also the first to be solved) or the notorious 8th problem (the Riemann hypothesis). There are other problems (notably the 5th) for which experts have traditionally agreed on a single interpretation and a solution to the accepted interpretation has been given, but for which there remain unsolved problems which are so closely related as to be, perhaps, part of what Hilbert intended. Sometimes Hilbert's statements were not precise enough to specify a particular problem but were suggestive enough so that certain problems of more contemporary origin seem to apply, e.g. most modern number theorists would probably see the 9th problem as referring to the (conjectural) Langlands correspondence on representations of the absolute Galois group of a number field. Still other problems (e.g. the 11th and the 16th) concern what are now flourishing mathematical subdisciplines, like the theories of quadratic forms and real algebraic curves.
There are two problems which are not only unresolved but may in fact be unresolvable by modern standards. The 6th problem concerns the axiomatization of physics, a goal that twentieth century developments of physics (including its recognition as a discipline independent from mathematics) seem to render both more remote and less important than in Hilbert's time. Also, the 4th problem concerns the foundations of geometry, in a manner which is now generally judged to be too vague to enable a definitive answer.
Remarkably, the other twenty-one problems have all received significant attention, and late into the twentieth century work on these problems was still considered to be of the greatest importance. Notably, Paul Cohen received the Fields Medal during 1966 for his work on the first problem, and the negative solution of the tenth problem during 1970 by Matiyasevich (completing work of Davis, Putnam and Robinson) generated similar acclaim. Aspects of these problems are still of great interest today.
Hilbert's twenty-three problems are:
| Problem | Brief explanation | Status | Year Solved |
|---|---|---|---|
| 1st | The continuum hypothesis (that is, there is no set whose cardinality is strictly between that of the integers and that of the real numbers) | Proven to be impossible to prove or disprove within the Zermelo–Fraenkel set theory with or without the Axiom of Choice (provided the Zermelo–Fraenkel set theory with or without the Axiom of Choice is consistent, i.e., contains no two theorems such that one is a negation of the other). There is no consensus on whether this is a solution to the problem. | 1963 |
| 2nd | Prove that the axioms of arithmetic are consistent. | There is no consensus on whether results of Gödel and Gentzen give a solution to the problem as stated by Hilbert. Gödel's second incompleteness theorem, proved in 1931, shows that no proof of its consistency can be carried out within arithmetic itself. Gentzen proved in 1936 that the consistency of arithmetic follows from the well-foundedness of the ordinal ε0. | 1936? |
| 3rd | Given any two polyhedra of equal volume, is it always possible to cut the first into finitely many polyhedral pieces which can be reassembled to yield the second? | Resolved. Result: no, proved using Dehn invariants. | 1900 |
| 4th | Construct all metrics where lines are geodesics. | Too vague to be stated resolved or not.[n 1] | – |
| 5th | Are continuous groups automatically differential groups? | Resolved by Andrew Gleason, depending on how the original statement is interpreted. If, however, it is understood as an equivalent of the Hilbert–Smith conjecture, it is still unsolved. | 1953? |
| 6th | Axiomatize all of physics | Unresolved. [n 2] | – |
| 7th | Is a b transcendental, for algebraic a ≠ 0,1 and irrational algebraic b ? | Resolved. Result: yes, illustrated by Gelfond's theorem or the Gelfond–Schneider theorem. | 1935 |
| 8th | The Riemann hypothesis ("the real part of any non-trivial zero of the Riemann zeta function is ½") and other prime number problems, among them Goldbach's conjecture and the twin prime conjecture | Unresolved. | – |
| 9th | Find most general law of the reciprocity theorem in any algebraic number field | Partially resolved.[n 3] | – |
| 10th | Find an algorithm to determine whether a given polynomial Diophantine equation with integer coefficients has an integer solution. | Resolved. Result: impossible, Matiyasevich's theorem implies that there is no such algorithm. | 1970 |
| 11th | Solving quadratic forms with algebraic numerical coefficients. | Partially resolved.[citation needed] | – |
| 12th | Extend the Kronecker–Weber theorem on abelian extensions of the rational numbers to any base number field. | Unresolved. | – |
| 13th | Solve all 7-th degree equations using continuous functions of two parameters. | Resolved. The problem was solved affirmatively by Vladimir Arnold based on work by Andrei Kolmogorov. [n 5] | 1957 |
| 14th | Is the ring of invariants of an algebraic group acting on a polynomial ring always finitely generated? | Resolved. Result: no, counterexample was constructed by Masayoshi Nagata. | 1959 |
| 15th | Rigorous foundation of Schubert's enumerative calculus. | Partially resolved.[citation needed] | – |
| 16th | Describe relative positions of ovals originating from a real algebraic curve and as limit cycles of a polynomial vector field on the plane. | Unresolved. | – |
| 17th | Expression of definite rational function as quotient of sums of squares | Resolved. Result: An upper limit was established for the number of square terms necessary.[citation needed] | 1927 |
| 18th | (a) Is there a polyhedron which admits only an anisohedral tiling in three dimensions? (b) What is the densest sphere packing? | (a) Resolved. Result: yes (by Karl Reinhardt). (b) Resolved by computer-assisted proof. Result: cubic close packing and hexagonal close packing, both of which have a density of approximately 74%.[n 6] | (a) 1928 (b) 1998 |
| 19th | Are the solutions of Lagrangians always analytic? | Resolved. Result: yes, proven by Ennio de Giorgi and, independently and using different methods, by John Forbes Nash. | 1957 |
| 20th | Do all variational problems with certain boundary conditions have solutions? | Resolved. A significant topic of research throughout the 20th century, culminating in solutions[citation needed] for the non-linear case. | – |
| 21st | Proof of the existence of linear differential equations having a prescribed monodromic group | Resolved. Result: Yes or no, depending on more exact formulations of the problem.[citation needed] | – |
| 22nd | Uniformization of analytic relations by means of automorphic functions | Resolved.[citation needed] | – |
| 23rd | Further development of the calculus of variations | Unresolved. |
