Statement
Formally, a function is space-constructible if and there exists a Turing machine which computes the function in space when starting with an input, where represents a string of s. Most of the common functions that we work with are space-constructible, including polynomials, exponents, and logarithms.
For every space-constructible function , there exists a language that is decidable in space but not in space .
Read more about this topic: Space Hierarchy Theorem
Famous quotes containing the word statement:
“He has the common feeling of his profession. He enjoys a statement twice as much if it appears in fine print, and anything that turns up in a footnote ... takes on the character of divine revelation.”
—Margaret Halsey (b. 1910)
“The new statement will comprise the skepticisms, as well as the faiths of society, and out of unbeliefs a creed shall be formed. For, skepticisms are not gratuitous or lawless, but are limitations of the affirmative statement, and the new philosophy must take them in, and make affirmations outside of them, just as much as must include the oldest beliefs.”
—Ralph Waldo Emerson (18031882)
“Most personal correspondence of today consists of letters the first half of which are given over to an indexed statement of why the writer hasnt written before, followed by one paragraph of small talk, with the remainder devoted to reasons why it is imperative that the letter be brought to a close.”
—Robert Benchley (18891945)