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:
“In Hell all the messages you ever left on answering machines will be played back to you.”
—Judy Horacek (b. 1961)
“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)
“The machine invades me all day.”
—Sharon Atkins, U.S. receptionist. As quoted in Working, book 2, by Studs Terkel (1973)
“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)