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:
“I was here first introduced to Joe.... He was a good-looking Indian, twenty-four years old, apparently of unmixed blood, short and stout, with a broad face and reddish complexion, and eyes, methinks, narrower and more turned up at the outer corners than ours, answering to the description of his race. Besides his underclothing, he wore a red flannel shirt, woolen pants, and a black Kossuth hat, the ordinary dress of the lumberman, and, to a considerable extent, of the Penobscot Indian.”
—Henry David Thoreau (1817–1862)
“A sound mind in a sound body, is a short, but full description of a happy state in this World: he that has these two, has little more to wish for; and he that wants either of them, will be little the better for anything else.”
—John Locke (1632–1704)
“The type of fig leaf which each culture employs to cover its social taboos offers a twofold description of its morality. It reveals that certain unacknowledged behavior exists and it suggests the form that such behavior takes.”
—Freda Adler (b. 1934)