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:
“Pilate with his question “What is truth?” is gladly trotted out these days as an advocate of Christ, so as to arouse the suspicion that everything known and knowable is an illusion and to erect the cross upon that gruesome background of the impossibility of knowledge.”
—Friedrich Nietzsche (1844–1900)
“I had many problems in my conduct of the office being contrasted with President Kennedy’s conduct in the office, with my manner of dealing with things and his manner, with my accent and his accent, with my background and his background. He was a great public hero, and anything I did that someone didn’t approve of, they would always feel that President Kennedy wouldn’t have done that.”
—Lyndon Baines Johnson (1908–1973)