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)
“Accountability in friendship is the equivalent of love without strategy.”
—Anita Brookner (b. 1938)
“The American people is out to get the kaiser. We are bending every nerve and every energy towards that end; anybody who gets in the way of the great machine the energy and devotion of a hundred million patriots is building towards the stainless purpose of saving civilization from the Huns will be mashed like a fly. I’m surprised that a collegebred man like you hasn’t more sense. Don’t monkey with the buzzsaw.”
—John Dos Passos (1896–1970)
“The playing adult steps sideward into another reality; the playing child advances forward to new stages of mastery....Child’s play is the infantile form of the human ability to deal with experience by creating model situations and to master reality by experiment and planning.”
—Erik H. Erikson (20th century)