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)
“The Sage of Toronto ... spent several decades marveling at the numerous freedoms created by a “global village” instantly and effortlessly accessible to all. Villages, unlike towns, have always been ruled by conformism, isolation, petty surveillance, boredom and repetitive malicious gossip about the same families. Which is a precise enough description of the global spectacle’s present vulgarity.”
—Guy Debord (b. 1931)
“It is possible—indeed possible even according to the old conception of logic—to give in advance a description of all ‘true’ logical propositions. Hence there can never be surprises in logic.”
—Ludwig Wittgenstein (1889–1951)