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:
“The parents who wish to lead a quiet life I would say: Tell your children that they are very naughty—much naughtier than most children; point to the young people of some acquaintances as models of perfection, and impress your own children with a deep sense of their own inferiority. You carry so many more guns than they do that they cannot fight you. This is called moral influence and it will enable you to bounce them as much as you please.”
—Samuel Butler (1835–1902)
“Accountability in friendship is the equivalent of love without strategy.”
—Anita Brookner (b. 1938)
“The machine has had a pernicious effect upon virtue, pity, and love, and young men used to machines which induce inertia, and fear, are near impotents.”
—Edward Dahlberg (1900–1977)
“The best way to teach a child restraint and generosity is to be a model of those qualities yourself. If your child sees that you want a particular item but refrain from buying it, either because it isn’t practical or because you can’t afford it, he will begin to understand restraint. Likewise, if you donate books or clothing to charity, take him with you to distribute the items to teach him about generosity.”
—Lawrence Balter (20th century)