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:
“No statement about God is simply, literally true. God is far more than can be measured, described, defined in ordinary language, or pinned down to any particular happening.”
—David Jenkins (b. 1925)
“The most distinct and beautiful statement of any truth must take at last the mathematical form.”
—Henry David Thoreau (18171862)
“The force of truth that a statement imparts, then, its prominence among the hordes of recorded observations that I may optionally apply to my own life, depends, in addition to the sense that it is argumentatively defensible, on the sense that someone like me, and someone I like, whose voice is audible and who is at least notionally in the same room with me, does or can possibly hold it to be compellingly true.”
—Nicholson Baker (b. 1957)