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:
“Gee, I wish we had one of them doomsday machines things.”
—Stanley Kubrick (b. 1928)
“The reality is that zero defects in products plus zero pollution plus zero risk on the job is equivalent to maximum growth of government plus zero economic growth plus runaway inflation.”
—Dixie Lee Ray (b. 1924)
“There is no question but that if Jesus Christ, or a great prophet from another religion, were to come back today, he would find it virtually impossible to convince anyone of his credentials ... despite the fact that the vast evangelical machine on American television is predicated on His imminent return among us sinners.”
—Peter Ustinov (b. 1921)
“I had a wonderful job. I worked for a big model agency in Manhattan.... When I got on the subway to go to work, it was like traveling into another world. Oh, the shops were beautiful, we had Bergdorf’s, Bendel’s, Bonwit’s, DePinna. The women wore hats and gloves. Another world. At home, it was cooking, cleaning, taking care of the kids, going to PTA, Girl Scouts. But when I got into the office, everything was different, I was different.”
—Estelle Shuster (b. c. 1923)