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:
“After the first powerful plain manifesto
The black statement of pistons, without more fuss
But gliding like a queen, she leaves the station.”
—Stephen Spender (19091995)
“Eroticism has its own moral justification because it says that pleasure is enough for me; it is a statement of the individuals sovereignty.”
—Mario Vargas Llosa (b. 1936)
“It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.”
—John Dewey (18591952)