Models Equivalent To The Turing Machine Model
See also: Turing machine equivalents, Register machine, and Post–Turing machineMany machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p. 159, cf Minsky (1967)). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the Church–Turing thesis hypothesizes this to be true for any kind of machine: that anything that can be "computed" can be computed by some Turing machine.)
A Turing machine is equivalent to a pushdown automaton that has been made more flexible and concise by relaxing the last-in-first-out requirement of its stack.
At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational power as the Turing machine model.
Common equivalent models are the multi-tape Turing machine, multi-track Turing machine, machines with input and output, and the non-deterministic Turing machine (NDTM) as opposed to the deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.
Read-only, right-moving Turing machines are equivalent to NDFAs (as well as DFAs by conversion using the NDFA to DFA conversion algorithm).
For practical and didactical intentions the equivalent register machine can be used as a usual assembly programming language.
Read more about this topic: Turing Machine
Famous quotes containing the words models, equivalent, machine and/or model:
“French rhetorical models are too narrow for the English tradition. Most pernicious of French imports is the notion that there is no person behind a text. Is there anything more affected, aggressive, and relentlessly concrete than a Parisan intellectual behind his/her turgid text? The Parisian is a provincial when he pretends to speak for the universe.”
—Camille Paglia (b. 1947)
“But then people don’t read literature in order to understand; they read it because they want to re-live the feelings and sensations which they found exciting in the past. Art can be a lot of things; but in actual practice, most of it is merely the mental equivalent of alcohol and cantharides.”
—Aldous Huxley (1894–1963)
“He is no more than the chief officer of the people, appointed by the laws, and circumscribed with definite powers, to assist in working the great machine of government erected for their use, and consequently subject to their superintendence.”
—Thomas Jefferson (1743–1826)
“Research shows clearly that parents who have modeled nurturant, reassuring responses to infants’ fears and distress by soothing words and stroking gentleness have toddlers who already can stroke a crying child’s hair. Toddlers whose special adults model kindliness will even pick up a cookie dropped from a peer’s high chair and return it to the crying peer rather than eat it themselves!”
—Alice Sterling Honig (20th century)