Machines Equivalent To The Turing Machine Model
Turing equivalence
Many 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). 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). (The Church-Turing thesis hypothesizes this to be true: that anything that can be “computed” can be computed by some Turing machine.)
The sequential-machine models
All of the following are called "sequential machine models" to distinguish them from "parallel machine models" (van Emde Boas (1990) p. 18).
Read more about this topic: Turing Machine Equivalents
Famous quotes containing the words machines, equivalent, machine and/or model:
“If men do not keep on speaking terms with children, they cease to be men, and become merely machines for eating and for earning money.”
—John Updike (b. 1932)
“In truth, politeness is artificial good humor, it covers the natural want of it, and ends by rendering habitual a substitute nearly equivalent to the real virtue.”
—Thomas Jefferson (1743–1826)
“But a man must keep an eye on his servants, if he would not have them rule him. 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. But it is found that the machine unmans the user. What he gains in making cloth, he loses in general power.”
—Ralph Waldo Emerson (1803–1882)
“There are very many characteristics which go into making a model civil servant. Prominent among them are probity, industry, good sense, good habits, good temper, patience, order, courtesy, tact, self-reliance, many deference to superior officers, and many consideration for inferiors.”
—Chester A. Arthur (1829–1886)