Description
In each state, the machine reads the bit under the head and executes the instructions in the following table (where Pn prints bit n, L and R are left and right respectively, and A and B mean "switch to that state").
-
A B 0 P1,R,B P2,L,A 1 P2,L,A P2,R,B 2 P1,L,A P0,R,A
The (2,3) Turing machine:
- Has no halt state;
- Is trivially related to 23 other machines by interchange of states, colors and directions.
Minsky (1967) briefly argues that standard (2,2) machines cannot be universal; thus, it might seem that the (2,3) Turing machine would be the smallest possible universal Turing machine (in terms of number of states times number of symbols). However, the results are not directly comparable, because Minsky only considers machines which explicitly halt, which the (2, 3) machine does not. More generally, almost all formal definitions of Turing machines differ in details irrelevant to their power, but perhaps relevant to what can be expressed using a given number of states and symbols; there is no single standard formal definition. The (2,3) Turing machine also requires an infinite non-repeating input, again making a direct comparison to earlier small Turing machines problematic. Therefore, though it may be true that the (2, 3) machine is in some sense the "smallest possible universal Turing machine", this has not been strictly proven, and the claim is open to debate.
The state of the head (up or down droplet) and the pattern of colour (orange, yellow and white) in a given row depends solely on the content of the row immediately above it.
Even though the machine has a head with only two states, and a tape that can hold only three colours (depending on the initial content of the tape), the machine's output can still be remarkably complex.
Read more about this topic: Wolfram's 2-state 3-symbol Turing Machine
Famous quotes containing the word description:
“Do not require a description of the countries towards which you sail. The description does not describe them to you, and to- morrow you arrive there, and know them by inhabiting them.”
—Ralph Waldo Emerson (1803–1882)
“The next Augustan age will dawn on the other side of the Atlantic. There will, perhaps, be a Thucydides at Boston, a Xenophon at New York, and, in time, a Virgil at Mexico, and a Newton at Peru. At last, some curious traveller from Lima will visit England and give a description of the ruins of St Paul’s, like the editions of Balbec and Palmyra.”
—Horace Walpole (1717–1797)
“Everything to which we concede existence is a posit from the standpoint of a description of the theory-building process, and simultaneously real from the standpoint of the theory that is being built. Nor let us look down on the standpoint of the theory as make-believe; for we can never do better than occupy the standpoint of some theory or other, the best we can muster at the time.”
—Willard Van Orman Quine (b. 1908)