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 with, problems, pointer, machine and/or model:
“I am always glad to think that my education was, for the most part, informal, and had not the slightest reference to a future business career. It left me free and untrammeled to approach my business problems without the limiting influence of specific training.”
—Alice Foote MacDougall (1867–1945)
“I have said many times, and it is literally true, that there is absolutely nothing that could keep me in business, if my job were simply business to me. The human problems which I deal with every day—concerning employees as well as customers—are the problems that fascinate me, that seem important to me.”
—Hortense Odlum (1892–?)
“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)
“The white man regards the universe as a gigantic machine hurtling through time and space to its final destruction: individuals in it are but tiny organisms with private lives that lead to private deaths: personal power, success and fame are the absolute measures of values, the things to live for. This outlook on life divides the universe into a host of individual little entities which cannot help being in constant conflict thereby hastening the approach of the hour of their final destruction.”
—Policy statement, 1944, of the Youth League of the African National Congress. pt. 2, ch. 4, Fatima Meer, Higher than Hope (1988)
“It has to be acknowledged that in capitalist society, with its herds of hippies, originality has become a sort of fringe benefit, a mere convention, accepted obsolescence, the Beatnik model being turned in for the Hippie model, as though strangely obedient to capitalist laws of marketing.”
—Mary McCarthy (1912–1989)