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:
“Friends broaden our horizons. They serve as new models with whom we can identify. They allow us to be ourselvesand accept us that way. They enhance our self-esteem because they think were okay, because we matter to them. And because they matter to usfor various reasons, at various levels of intensitythey enrich the quality of our emotional life.”
—Judith Viorst (20th century)
“I started off rapping for people just like myself, people who were in awe of wealth and flash. It was a conversation between me and them. But now most of those who buy my records are listening in on others conversation. They are the aural equivalent of voyeurs, thrilled at this crazy world that has nothing to do with their experience.”
—Ice-T [Tracy Marrow], U.S. rap musician. Observer (London, Oct. 27, 1991)
“Man is a shrewd inventor, and is ever taking the hint of a new machine from his own structure, adapting some secret of his own anatomy in iron, wood, and leather, to some required function in the work of the world.”
—Ralph Waldo Emerson (18031882)
“...that absolutely everything beloved and cherished of the bourgeoisie, the conservative, the cowardly, and the impotentthe State, family life, secular art and sciencewas consciously or unconsciously hostile to the religious idea, to the Church, whose innate tendency and permanent aim was the dissolution of all existing worldly orders, and the reconstitution of society after the model of the ideal, the communistic City of God.”
—Thomas Mann (18751955)