Machine Model
The exact machine model used to define DTIME can vary without affecting the power of the resource. Results in the literature often use multitape Turing machines, particularly when discussing very small time classes. In particular, a multitape deterministic Turing machine can never provide more than a quadratic time speedup over a singletape machine (Papadimitriou 1994, Thrm. 2.1).
Multiplicative constants in the amount of time used do not change the power of DTIME classes; a constant multiplicative speedup can always be obtained by increasing the number of states in the finite state control. In the statement of Papadimitriou (1994, Thrm. 2.2), for a language L,
- Let L DTIME(f(n)). Then, for any > 0, L DTIME(f'(n)), where f'(n) = f(n) + n + 2.
Read more about this topic: DTIME
Famous quotes containing the words machine and/or model:
“The momentary charge at Balaklava, in obedience to a blundering command, proving what a perfect machine the soldier is, has, properly enough, been celebrated by a poet laureate; but the steady, and for the most part successful, charge of this man, for some years, against the legions of Slavery, in obedience to an infinitely higher command, is as much more memorable than that as an intelligent and conscientious man is superior to a machine. Do you think that that will go unsung?”
—Henry David Thoreau (1817–1862)
“Research shows clearly that parents who have modeled nurturant, reassuring responses to infants’ fears and distress by soothing words and stroking gentleness have toddlers who already can stroke a crying child’s hair. Toddlers whose special adults model kindliness will even pick up a cookie dropped from a peer’s high chair and return it to the crying peer rather than eat it themselves!”
—Alice Sterling Honig (20th century)