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:
“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)
“He that writes to himself writes to an eternal public. That statement only is fit to be made public, which you have come at in attempting to satisfy your own curiosity.”
—Ralph Waldo Emerson (18031882)
“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)