Background
Both theorems use the notion of a time-constructible function. A function is time-constructible if there exists a deterministic Turing machine such that for every, if the machine is started with an input of n ones, it will halt after precisely steps. All polynomials with non-negative integral coefficients are time-constructible, as are exponential functions such as .
Read more about this topic: Time Hierarchy Theorem
Famous quotes containing the word background:
“Silence is the universal refuge, the sequel to all dull discourses and all foolish acts, a balm to our every chagrin, as welcome after satiety as after disappointment; that background which the painter may not daub, be he master or bungler, and which, however awkward a figure we may have made in the foreground, remains ever our inviolable asylum, where no indignity can assail, no personality can disturb us.”
—Henry David Thoreau (1817–1862)
“... every experience in life enriches one’s background and should teach valuable lessons.”
—Mary Barnett Gilson (1877–?)
“In the true sense one’s native land, with its background of tradition, early impressions, reminiscences and other things dear to one, is not enough to make sensitive human beings feel at home.”
—Emma Goldman (1869–1940)