Problems With The Pointer Machine Model
Use of the model in complexity theory: van Emde Boas (1990) expresses concern that this form of abstract model is:
- "an interesting theoretical model, but ... its attractiveness as a fundamental model for complexity theory is questionable. Its time measure is based on uniform time in a context where this measure is known to underestimate the true time complexity. The same observation holds for the space measure for the machine" (van Emde Boas (1990) p. 35)
Gurevich 1988 also expresses concern:
- "Pragmatically speaking, the Schönhage model provides a good measure of time complexity at the current state of the art (though I would prefer something along the lines of the random access computers of Angluin and Valiant)" (Gurevich (1988) p. 6 with reference to Angluin D. and Valiant L. G., Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings", Journal of Computer and System Sciences 18 (1979) 155-193.)
The fact that, in §3 and §4 (pp. 494–497), Schönhage himself (1980) demonstrates the real-time equivalences of his two Random Access Machine models "RAM0" and "RAM1" leads one to question the necessity of the SMM for complexity studies.
Potential uses for the model: However, Schönhage (1980) demonstrates in his §6, Integer-multiplication in linear time. And Gurevich wonders whether or not the "parallel KU machine" "resembles somewhat the human brain" (Gurevich (1988) p. 5)
Read more about this topic: Pointer Machine
Famous quotes containing the words problems, pointer, machine and/or model:
“The man who is forever disturbed about the condition of humanity either has no problems of his own or has refused to face them.”
—Henry Miller (1891–1980)
“The hardiest skeptic who has seen a horse broken, a pointer trained, or has visited a menagerie or the exhibition of the Industrious Fleas, will not deny the validity of education. “A boy,” says Plato, “is the most vicious of all beasts;” and in the same spirit the old English poet Gascoigne says, “A boy is better unborn than untaught.””
—Ralph Waldo Emerson (1803–1882)
“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)
“For an artist to marry his model is as fatal as for a gourmet to marry his cook: the one gets no sittings, and the other gets no dinners.”
—Oscar Wilde (1854–1900)